oj.uz

Submission #7915

# Submission time Handle Problem Language Result Execution time Memory
7915 2014-08-25T07:47:42 Z gs14004 허수아비 (JOI14_scarecrows) C++
15 / 100
 4000 ms 8040 KB 
#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);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4612 KB Output is correct
2 Correct 24 ms 4612 KB Output is correct
3 Correct 24 ms 4612 KB Output is correct
4 Correct 28 ms 4612 KB Output is correct
5 Correct 32 ms 4612 KB Output is correct
6 Correct 28 ms 4612 KB Output is correct
7 Correct 28 ms 4612 KB Output is correct
8 Correct 28 ms 4612 KB Output is correct
9 Correct 28 ms 4612 KB Output is correct
10 Correct 20 ms 4612 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 4876 KB Output is correct
2 Correct 384 ms 4876 KB Output is correct
3 Correct 380 ms 4876 KB Output is correct
4 Correct 380 ms 4876 KB Output is correct
5 Correct 384 ms 4876 KB Output is correct
6 Correct 384 ms 4876 KB Output is correct
7 Correct 384 ms 4876 KB Output is correct
8 Correct 384 ms 4876 KB Output is correct
9 Correct 376 ms 4876 KB Output is correct
10 Correct 388 ms 4876 KB Output is correct
11 Correct 384 ms 4876 KB Output is correct
12 Correct 316 ms 4876 KB Output is correct

Subtask #3
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4000 ms 8040 KB Program timed out
2 Halted 0 ms 0 KB -