1000——Educational Codeforces Round 46 (Rated for Div. 2)

codeforces

2018.6.18 参加（A，B，C比赛结束后2分钟A的）
2018.6.19 整理

http://codeforces.com/contest/1000

A：
模拟

B：
放的点一定是 原来点的左边或者右边，枚举。

C：
差分，判断。

D：

代码：

C：

 #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 500100;
struct Node{
    LL x,val;
    bool operator < (const Node &A) const {
        return x == A.x ? val > A.val : x < A.x;
    }
}A[N];
LL cnt[N];
int main () {
    int n = read();
    int p = 0;
    for (int i=1; i<=n; ++i) {
        LL l,r;
        scanf("%I64d%I64d",&l,&r);
        A[++p].x = l,A[p].val = 1;
        A[++p].x = r,A[p].val = -1;
    }
    sort(A+1,A+p+1);
    int tot = 1,c = 0;
    for (int i=2; i<=p; ++i) {
        if (A[i].x == A[tot].x && A[i].val == A[tot].val) c++;
        else {
            if (A[tot].val == -1) A[tot].val -= c;
            else A[tot].val += c;
            c = 0,A[++tot] = A[i];
        }
    }
    if (A[tot].val == -1) A[tot].val -= c;
    else A[tot].val += c;
    int now = A[1].val;
    for (int i=2; i<=tot; ++i) {
        if (A[i-1].val > 0) cnt[now] += A[i].x-A[i-1].x;
        else cnt[now] += A[i].x-A[i-1].x-1;
        if (A[i].val < 0) cnt[now]++;
        now += A[i].val;
    }
    for (int i=1; i<=n; ++i) {
        printf("%I64d ",cnt[i]);
    }
    return 0;
}