Submission #15138

#	Time	Username	Problem	Language	Result	Execution time	Memory
15138		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,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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 85