oj.uz

Submission #15137

# Submission time Handle Problem Language Result Execution time Memory
15137 2015-07-11T14:24:33 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,siz,ind[2*max_n];
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;
    siz = n/sq + (n%sq==0 ? 0 : 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;
    }
    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;
    }
    return;
}
void Push(int p,int front,int rear,int v) {
    ind[p] ++;
    if(front == rear) return;
    int mid = (front+rear)/2;
    if(v <= mid) Push(2*p,front,mid,v);
    else Push(2*p+1,mid+1,rear,v);
}
int segadd(int p,int front,int rear,int head,int tail) {
    if(front > tail || head > rear) return 0;
    if(head <= front && rear <= tail) return ind[p];
    int mid = (front+rear)/2;
    return segadd(2*p,front,mid,head,tail) + segadd(2*p+1,mid+1,rear,head,tail);
}
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);
    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(1);
    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) Push(1,0,n-1,now.tail);
        else ret += segadd(1,0,n-1,now.head,now.tail);
    }
    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 45 ms 6568 KB Output is correct
2 Correct 45 ms 6568 KB Output is correct
3 Correct 45 ms 6568 KB Output is correct
4 Correct 45 ms 6568 KB Output is correct
5 Correct 41 ms 6568 KB Output is correct
6 Correct 45 ms 6568 KB Output is correct
7 Correct 42 ms 6568 KB Output is correct
8 Correct 45 ms 6568 KB Output is correct
9 Correct 46 ms 6568 KB Output is correct
10 Correct 29 ms 6568 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 6892 KB Output is correct
2 Correct 568 ms 6892 KB Output is correct
3 Correct 560 ms 6892 KB Output is correct
4 Correct 558 ms 6892 KB Output is correct
5 Correct 565 ms 6892 KB Output is correct
6 Correct 571 ms 6892 KB Output is correct
7 Correct 567 ms 6892 KB Output is correct
8 Correct 552 ms 6892 KB Output is correct
9 Correct 559 ms 6892 KB Output is correct
10 Correct 571 ms 6892 KB Output is correct
11 Correct 567 ms 6892 KB Output is correct
12 Correct 463 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 -