oj.uz

Submission #7918

# Submission time Handle Problem Language Result Execution time Memory
7918 2014-08-25T08:28:07 Z gs14004 허수아비 (JOI14_scarecrows) C++
100 / 100
 1696 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 < 200){
        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 12 ms 4876 KB Output is correct
2 Correct 16 ms 4876 KB Output is correct
3 Correct 16 ms 4876 KB Output is correct
4 Correct 12 ms 4876 KB Output is correct
5 Correct 16 ms 4876 KB Output is correct
6 Correct 16 ms 4876 KB Output is correct
7 Correct 16 ms 4876 KB Output is correct
8 Correct 12 ms 4876 KB Output is correct
9 Correct 12 ms 4876 KB Output is correct
10 Correct 16 ms 4876 KB Output is correct
11 Correct 8 ms 4876 KB Output is correct
12 Correct 8 ms 4876 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1132 ms 18604 KB Output is correct
2 Correct 1696 ms 18604 KB Output is correct
3 Correct 1148 ms 18604 KB Output is correct
4 Correct 1020 ms 18604 KB Output is correct
5 Correct 1220 ms 18604 KB Output is correct
6 Correct 1436 ms 18604 KB Output is correct
7 Correct 1560 ms 18604 KB Output is correct
8 Correct 1668 ms 18604 KB Output is correct
9 Correct 1144 ms 18604 KB Output is correct
10 Correct 1232 ms 18604 KB Output is correct
11 Correct 1456 ms 18604 KB Output is correct
12 Correct 1620 ms 18604 KB Output is correct
13 Correct 1672 ms 18604 KB Output is correct
14 Correct 1020 ms 18604 KB Output is correct
15 Correct 1440 ms 18604 KB Output is correct
16 Correct 1680 ms 18604 KB Output is correct
17 Correct 884 ms 13720 KB Output is correct
18 Correct 1616 ms 18604 KB Output is correct
19 Correct 1552 ms 18604 KB Output is correct
20 Correct 1544 ms 18604 KB Output is correct