제출 #7915

#제출 시각아이디문제언어결과실행 시간메모리
7915gs14004허수아비 (JOI14_scarecrows)C++98
15 / 100
4000 ms8040 KiB
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
typedef pair<int,int> pi;

struct pt{int x,y;}pos[200005];
int cmp1(pt a, pt b){return a.x<b.x;}
int cmp2(pt a, pt b){return a.y<b.y;}

int a[200005],n;

int lim, tree[270000];
void initTree(int n){
    for(lim = 1; lim <= n; lim <<= 1);
    memset(tree,0,sizeof(tree));
}
void add(int x){
    while (x <= lim) {
        tree[x]++;
        x += x & -x;
    }
}
int sum(int x){
    int res = 0;
    while (x) {
        res += tree[x];
        x -= x & -x;
    }
    return res;
}

long long f(int s, int e){
    if(s == e) return 0;
    int m = (s+e)/2;
    long long res = f(s,m) + f(m+1,e);
    
    initTree(n+1);
    set<pi> s_left, s_right, s_right_old;
    set<pi>::iterator it;
    
    for (int i=m; i>=s; i--) {
        it = s_left.upper_bound(pi(a[i],0));
        int lim;
        if(it == s_left.end()) lim = n+1;
        else lim = (*it).first - 1;
        s_left.insert(pi(a[i],lim));
    }
    
    for (int i=m+1; i<=e; i++) {
        it = s_right_old.upper_bound(pi(a[i],0));
        int lim;
        if(it == s_right_old.begin()) lim = -1;
        else{
            it--;
            lim = (*it).first;
        }
        s_right_old.insert(pi(a[i],lim));
    }
    
    for (it = s_right_old.begin(); it != s_right_old.end(); it++) {
        pi x = *it;
        swap(x.first,x.second);
        s_right.insert(x);
    }
    s_left.insert(pi(1e9,1e9));
    s_right.insert(pi(1e9,1e9));
    for (int i=s; i<=e; i++) {
        if((*s_left.begin()).first < (*s_right.begin()).first){
            it = s_left.begin();
            res += sum((*it).second) - sum((*it).first - 1);
            s_left.erase(it);
        }
        else{
            it = s_right.begin();
            add((*it).second);
            s_right.erase(it);
        }
    }
    return res;
}

int main(){
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d %d",&pos[i].x,&pos[i].y);
    }
    sort(pos,pos+n,cmp2);
    for (int i=0; i<n; i++) {
        pos[i].y = i+1;
    }
    sort(pos,pos+n,cmp1);
    for (int i=0; i<n; i++) {
        a[i] = pos[i].y;
    }
    long long r = f(0,n-1);
    printf("%lld",r);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...