oj.uz

Submission #15139

# Submission time Handle Problem Language Result Execution time Memory
15139 2015-07-11T14:42:41 Z Fakeable 허수아비 (JOI14_scarecrows) C++
100 / 100
 1335 ms 19004 KB 
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;

typedef long long ll;
const int max_n = 200200;
int n,sq=450,ind[2*max_n],lim;
ll ans, upright[max_n];
struct point {
    int x,y;
    point() {}
    point(int x_,int y_) {
        x = x_, y = y_;
    }
} p[max_n];
bool cmp(point X,point Y) {
    return X.x < Y.x;
}
struct element {
    int head,tail;
    bool type;
    element(int head_,int tail_,bool type_) {
        head = head_, tail = tail_, type = type_;
    }
    bool operator <(const element & comp) const {
        return (head == comp.head) ? (type > comp.type) : (head < comp.head);
    }
};
set<point> s[500];
set<point>::iterator it,it_;

void input() {
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(lim = 1;lim<=n+1;lim <<= 1);
    for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y;
    sort(p,p+n,cmp);
    return;
}
void compress() {
    vector<int> v;
    for(int i=0;i<n;i++) v.push_back(p[i].x);
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++) {
        int lo = 0, hi = n-1;
        while(lo<hi) {
            int mid = (lo+hi-1)/2;
            if(v[mid] < p[i].x) lo = mid+1;
            else hi = mid;
        }
        p[i].x = lo+1;
    }
    v.clear();
    for(int i=0;i<n;i++) v.push_back(p[i].y);
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++) {
        int lo = 0, hi = n-1;
        while(lo < hi) {
            int mid = (lo+hi-1)/2;
            if(v[mid] < p[i].y) lo = mid+1;
            else hi = mid;
        }
        p[i].y = lo+1;
    }
    return;
}
inline void add(int x) {
    while(x <= lim) {
        ind[x] ++;
        x += x & -x;
    }
    return;
}
inline ll bitadd(int x) {
    ll ret = 0;
    while(x) {
        ret += ind[x];
        x -= x & -x;
    }
    return ret;
}
ll solve(int fr,int re) {
    if(re - fr < 450) {
        ll ret = 0;
        for(int i=fr;i<=re;i++) {
            int highest = 1000000001;
            for(int j=i+1;j<=re;j++) {
                if(p[i].y < p[j].y && p[j].y < highest) {
                    ret ++;
                    highest = p[j].y;
                }
            }
        }
        return ret;
    }
    int m = (fr+re)/2;
    ll ret = solve(fr,m) + solve(m+1,re);
    set<int> lefts, rights;
    set<int>::iterator it;
    vector<element> v;
    lefts.insert(n+1);
    for(int i=m;i>=fr;i--) {
        int now = p[i].y;
        it = lefts.lower_bound(now);
        v.push_back(element(now,(*it)-1,0));
        lefts.insert(now);
    }
    rights.insert(0);
    for(int i=m+1;i<=re;i++) {
        int now = -p[i].y;
        it =rights.lower_bound(now);
        v.push_back(element(-(*it)+1,-now,1));
        rights.insert(now);
    }
    sort(v.begin(),v.end());
    memset(ind,0,sizeof(ind));
    for(int i=0;i<(int)v.size();i++) {
        element now = v[i];
        if(now.type) add(now.tail);
        else ret += bitadd(now.tail) - bitadd(now.head-1);
    }
    return ret;
}
int main() {
    input();
    compress();
    cout<<solve(0,n-1)<<endl;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6436 KB Output is correct
2 Correct 0 ms 6436 KB Output is correct
3 Correct 1 ms 6436 KB Output is correct
4 Correct 0 ms 6436 KB Output is correct
5 Correct 0 ms 6436 KB Output is correct
6 Correct 0 ms 6436 KB Output is correct
7 Correct 0 ms 6436 KB Output is correct
8 Correct 0 ms 6436 KB Output is correct
9 Correct 1 ms 6436 KB Output is correct
10 Correct 0 ms 6436 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6892 KB Output is correct
2 Correct 16 ms 6892 KB Output is correct
3 Correct 13 ms 6892 KB Output is correct
4 Correct 9 ms 6892 KB Output is correct
5 Correct 12 ms 6892 KB Output is correct
6 Correct 14 ms 6892 KB Output is correct
7 Correct 14 ms 6892 KB Output is correct
8 Correct 8 ms 6892 KB Output is correct
9 Correct 14 ms 6892 KB Output is correct
10 Correct 15 ms 6892 KB Output is correct
11 Correct 17 ms 6892 KB Output is correct
12 Correct 9 ms 6892 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 18968 KB Output is correct
2 Correct 1335 ms 19004 KB Output is correct
3 Correct 924 ms 18968 KB Output is correct
4 Correct 835 ms 18968 KB Output is correct
5 Correct 971 ms 18968 KB Output is correct
6 Correct 1153 ms 18968 KB Output is correct
7 Correct 1242 ms 18968 KB Output is correct
8 Correct 1310 ms 18968 KB Output is correct
9 Correct 813 ms 18968 KB Output is correct
10 Correct 912 ms 18968 KB Output is correct
11 Correct 1051 ms 18968 KB Output is correct
12 Correct 1246 ms 18976 KB Output is correct
13 Correct 1323 ms 18996 KB Output is correct
14 Correct 757 ms 18968 KB Output is correct
15 Correct 1082 ms 18968 KB Output is correct
16 Correct 1330 ms 18980 KB Output is correct
17 Correct 718 ms 14216 KB Output is correct
18 Correct 1260 ms 18972 KB Output is correct
19 Correct 1246 ms 18968 KB Output is correct
20 Correct 1195 ms 18968 KB Output is correct