Color the ball HDU - 1556

N名同学拍成一排，编号为1，2，3，4 …… N。现在有一位老师需要检查所有同学的出勤情况，他会进行点名，每次给出两个数a,b，并且保证a小于等于b，这个区间内的所有同学都会被点名一次，老师会进行N次点名，请问点名结束后，每位同学被点名的总次数是多少

Input

每个测试实例第一行为一个整数N,(N <= 100000).

接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。

当N = 0，输入结束。

Output

每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。

Input Sample

Output Sample

1 1 1

3 2 1

分析

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10,INF=0x3f3f3f3f;

int n,m,a,b,d[N];

int main(){

    while(cin>>n && n){

        memset(d,0,sizeof(d));

        m=n; while (m--){

            cin>>a>>b;

            d[a] ++;

            d[b+1] --;

        }

        for(int i=1; i<=n; i++) d[i]+=d[i-1];

        for(int i=1; i<=n; i++) cout<<d[i]<<" \n"[i==n];

    }

}

巴特西

Color the ball HDU - 1556 _差分

Input

Output

Input Sample

Output Sample

分析

最新文章

热门文章