oj.uz

Submission #7917

# Submission time Handle Problem Language Result Execution time Memory
7917 2014-08-25T08:26:37 Z gs14004 허수아비 (JOI14_scarecrows) C++
100 / 100
 1808 ms 18604 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(){
    for(lim = 1; lim <= n+1; 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){
    long long res = 0;
    if(e - s < 100){
        for (int i=s; i<=e; i++) {
            int lower=a[i];
            int upper=1987654321;
            for (int j=i+1; j<=e; j++) {
                if(upper>a[j] && a[j]>lower){
                    upper=a[j];
                    res++;
                }
            }
        }
        return res;
    }
    int m = (s+e)/2;
    res = f(s,m) + f(m+1,e);
    
    initTree();
    set<pi> s_left, s_right, s_right_old;
    set<pi> ::iterator it,it2;
    int lim;
    
    for (int i=m; i>=s; i--) {
        it = s_left.upper_bound(pi(a[i],0));
        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));
        if(it == s_right_old.begin()) lim = -1;
        else{
            it--;
            lim = (*it).first;
        }
        s_right_old.insert(pi(a[i],lim));
        s_right.insert(pi(lim,a[i]));
    }
    
    s_left.insert(pi(1e6,1e6));
    s_right.insert(pi(1e6,1e6));
    it = s_left.begin();
    it2 = s_right.begin();
    
    for (int i=s; i<=e; i++) {
        if((*it).first < (*it2).first){
            res += sum((*it).second) - sum((*it).first - 1);
            it++;
        }
        else{
            add((*it2).second);
            it2++;
        }
    }
    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 0 ms 4612 KB Output is correct
2 Correct 0 ms 4612 KB Output is correct
3 Correct 0 ms 4612 KB Output is correct
4 Correct 0 ms 4612 KB Output is correct
5 Correct 0 ms 4612 KB Output is correct
6 Correct 0 ms 4612 KB Output is correct
7 Correct 0 ms 4612 KB Output is correct
8 Correct 0 ms 4612 KB Output is correct
9 Correct 0 ms 4612 KB Output is correct
10 Correct 0 ms 4612 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4876 KB Output is correct
2 Correct 16 ms 4876 KB Output is correct
3 Correct 20 ms 4876 KB Output is correct
4 Correct 12 ms 4876 KB Output is correct
5 Correct 12 ms 4876 KB Output is correct
6 Correct 20 ms 4876 KB Output is correct
7 Correct 20 ms 4876 KB Output is correct
8 Correct 12 ms 4876 KB Output is correct
9 Correct 20 ms 4876 KB Output is correct
10 Correct 16 ms 4876 KB Output is correct
11 Correct 20 ms 4876 KB Output is correct
12 Correct 12 ms 4876 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1240 ms 18604 KB Output is correct
2 Correct 1808 ms 18604 KB Output is correct
3 Correct 1252 ms 18604 KB Output is correct
4 Correct 1140 ms 18604 KB Output is correct
5 Correct 1332 ms 18604 KB Output is correct
6 Correct 1556 ms 18604 KB Output is correct
7 Correct 1712 ms 18604 KB Output is correct
8 Correct 1788 ms 18604 KB Output is correct
9 Correct 1264 ms 18604 KB Output is correct
10 Correct 1364 ms 18604 KB Output is correct
11 Correct 1576 ms 18604 KB Output is correct
12 Correct 1732 ms 18604 KB Output is correct
13 Correct 1792 ms 18604 KB Output is correct
14 Correct 1120 ms 18604 KB Output is correct
15 Correct 1560 ms 18604 KB Output is correct
16 Correct 1800 ms 18604 KB Output is correct
17 Correct 996 ms 13720 KB Output is correct
18 Correct 1740 ms 18604 KB Output is correct
19 Correct 1676 ms 18604 KB Output is correct
20 Correct 1664 ms 18604 KB Output is correct