Submission #15137

#	Time	Username	Problem	Language	Result	Execution time	Memory
15137		Fakeable	허수아비 (JOI14_scarecrows)	C++98	15 / 100	4000 ms	8100 KiB

scarecrows

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 85