oj.uz

Submission #15138

# Submission time Handle Problem Language Result Execution time Memory
15138 2015-07-11T14:34:38 Z Fakeable 허수아비 (JOI14_scarecrows) C++
15 / 100
 4000 ms 8100 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(fr >= re) return 0;
    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 44 ms 6568 KB Output is correct
2 Correct 45 ms 6568 KB Output is correct
3 Correct 44 ms 6568 KB Output is correct
4 Correct 44 ms 6568 KB Output is correct
5 Correct 45 ms 6568 KB Output is correct
6 Correct 45 ms 6568 KB Output is correct
7 Correct 44 ms 6568 KB Output is correct
8 Correct 45 ms 6568 KB Output is correct
9 Correct 44 ms 6568 KB Output is correct
10 Correct 28 ms 6568 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 6892 KB Output is correct
2 Correct 555 ms 6892 KB Output is correct
3 Correct 554 ms 6892 KB Output is correct
4 Correct 548 ms 6892 KB Output is correct
5 Correct 553 ms 6892 KB Output is correct
6 Correct 559 ms 6892 KB Output is correct
7 Correct 563 ms 6892 KB Output is correct
8 Correct 556 ms 6892 KB Output is correct
9 Correct 562 ms 6892 KB Output is correct
10 Correct 559 ms 6892 KB Output is correct
11 Correct 563 ms 6892 KB Output is correct
12 Correct 457 ms 6892 KB Output is correct

Subtask #3
0.0 / 85.0

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