#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;
}
Compilation message
scarecrows.cpp: In function ‘void input()’:
scarecrows.cpp:34:5: error: ‘ios_base’ has not been declared
ios_base::sync_with_stdio(false);
^
scarecrows.cpp:35:5: error: ‘cin’ was not declared in this scope
cin>>n;
^
scarecrows.cpp: In function ‘ll solve(int, int)’:
scarecrows.cpp:103:29: error: ‘memset’ was not declared in this scope
memset(ind,0,sizeof(ind));
^
scarecrows.cpp: In function ‘int main()’:
scarecrows.cpp:114:5: error: ‘cout’ was not declared in this scope
cout<<solve(0,n-1)<<endl;
^
scarecrows.cpp:114:25: error: ‘endl’ was not declared in this scope
cout<<solve(0,n-1)<<endl;
^
