#include<stdio.h>
#include<algorithm>
using namespace std;
int c,w,n,w1,w2,top,arr1[200010],arr2[200010],tree[200010],go[200010],cnt[200010];
struct data{
int x,y;
bool operator<(const data&r)const{
return x<r.x;
}
}a[200010];
struct data5{
int x,y;
}a2[200010];
struct data2{
int x,y;
bool operator<(const data2&r)const{
return y>r.y;
}
}b[200010];
struct data3{
int x,pos;
}st[200010];
struct data4{
int x,y;
bool operator<(const data4&r)const{
return y<r.y;
}
}p[200010];
int dfs(int x)
{
if(tree[x]==0) return x;
tree[x]=dfs(tree[x]);
cnt[x]+=c; c++;
}
int pro(int x,int y)
{
int i,j,ky=b[(x+y)/2+1].y,r=1,s2=1,dap=0,w1=0,w2=0,w=0;
cnt[0]=-1;
for(i=x;i<=y;i++)
{
if(a[i].y>ky)
{
for(j=s2;j<=w2;j++) go[arr2[j]]=i; s2=w2+1;
arr1[++w1]=i;
}
else
{
arr2[++w2]=i;
}
}
st[0].x=2147483647; top=0;
for(i=1;i<=w2;i++)
{
while(st[top].x<a[arr2[i]].y)
{
w++; p[w].x=st[top].pos; p[w].y=a[arr2[i]].x;
top--;
}
top++; st[top].x=a[arr2[i]].y; st[top].pos=arr2[i];
}
for(i=1;i<=top;i++){w++; p[w].x=st[i].pos; p[w].y=2147483647;}
sort(p+1,p+w+1);
top=0; st[0].x=-1;
for(j=1;j<=w;j++)
{
for(i=r;i<=w1;i++)
{
if(a[arr1[i]].x>p[j].y) break;
while(st[top].x>a[arr1[i]].y)
{
tree[st[top].pos]=arr1[i];
top--;
}
top++; st[top].x=a[arr1[i]].y; st[top].pos=arr1[i];
}
r=i;
if(go[p[j].x]>arr1[r-1] || go[p[j].x]==0) continue;
if(tree[go[p[j].x]]==0){dap++; continue;}
c=0; dfs(go[p[j].x]); dap+=cnt[go[p[j].x]]+2;
}
for(i=1;i<=w1;i++) a2[x+i-1].x=a[arr1[i]].x, a2[x+i-1].y=a[arr1[i]].y;
for(i=w2;i>=1;i--) a2[y+i-w2].x=a[arr2[i]].x, a2[y+i-w2].y=a[arr2[i]].y;
for(i=x;i<=y;i++) a[i].x=a2[i].x, a[i].y=a2[i].y;
for(i=x;i<=y;i++) cnt[i]=0, tree[i]=0, go[i]=0;
return dap;
}
int divide(int x,int y)
{
if(x==y) return 0;
return pro(x,y)+divide(x,(x+y)/2)+divide((x+y)/2+1,y);
}
int main()
{
int i,dap;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&a[i].x,&a[i].y);
b[i].x=a[i].x; b[i].y=a[i].y;
}
sort(b+1,b+n+1); sort(a+1,a+n+1);
dap=divide(1,n);
printf("%d",dap);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
12812 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
12812 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
12812 KB |
Output is correct |
| 2 |
Memory limit exceeded |
56 ms |
262144 KB |
Memory limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
148 ms |
14252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
