#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=2.5e5, mxC=2500;
int n, x[mxN], y[mxN], a[mxC][mxC], pa[mxC+1][mxC+1], uhbx[mxC+1], uhby[mxC+1], lhbx[mxC+1], lhby[mxC+1];
inline int spa(int x1, int y1, int x2, int y2) {
return pa[x2][y2]-pa[x1][y2]-pa[x2][y1]+pa[x1][y1];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n; ++i) {
cin >> x[i] >> y[i], --x[i], --y[i];
a[x[i]][y[i]]=i+1;
pa[x[i]+1][y[i]+1]=1;
}
for(int i=1; i<=mxC; ++i) {
for(int j=1; j<=mxC; ++j)
pa[i][j]+=pa[i][j-1];
for(int j=1; j<=mxC; ++j)
pa[i][j]+=pa[i-1][j];
uhbx[i]=uhbx[i-1];
for(int j=uhbx[i]?y[uhbx[i]-1]-1:mxC-1; j>=0; --j)
uhbx[i]=a[i-1][j]?a[i-1][j]:uhbx[i];
uhby[i]=uhby[i-1];
for(int j=uhby[i]?x[uhby[i]-1]-1:mxC-1; j>=0; --j)
uhby[i]=a[j][i-1]?a[j][i-1]:uhby[i];
}
for(int i=mxC-1; i>=0; --i) {
lhbx[i]=lhbx[i+1];
for(int j=lhbx[i]?y[lhbx[i]-1]+1:0; j<mxC; ++j)
lhbx[i]=a[i][j]?a[i][j]:lhbx[i];
lhby[i]=lhby[i+1];
for(int j=lhby[i]?x[lhby[i]-1]+1:0; j<mxC; ++j)
lhby[i]=a[j][i]?a[j][i]:lhby[i];
}
map<pair<ll, ll>, int> hax1;
for(int i=0; i<n; ++i) {
int a1=pa[x[i]][y[i]], a2=spa(x[i]+1, y[i]+1, mxC, mxC), ans=-a1-a2-2, d=2, a3;
if(a1+a2<n-1) {
int uh1=uhbx[x[i]]-1, uh2=uhby[y[i]]-1, lh1=lhby[y[i]+1]-1, lh2=lhbx[x[i]+1]-1;
if(!a1)
uh1=uh2=i;
if(!a2)
lh1=lh2=i;
ll hax2=(ll)uh1*mxN+uh2, hax3=(ll)lh1*mxN+lh2;
if(hax1.find({hax2, hax3})==hax1.end()) {
while(1) {
++d;
a3=pa[x[lh1]][y[lh2]]+spa(x[uh2]+1, y[uh1]+1, mxC, mxC)-spa(x[uh2]+1, y[uh1]+1, x[lh1], y[lh2]);
ans-=a3;
if(a3>=n)
break;
int nuh1=uhbx[x[lh1]]-1, nuh2=uhby[y[lh2]]-1;
lh1=lhby[y[uh1]+1]-1, lh2=lhbx[x[uh2]+1]-1, uh1=nuh1, uh2=nuh2;
}
// if(hax1[{hax2, hax3}]&&hax1[{hax2, hax3}]!=ans+a1+a2+2+(d-2)*n)
// cout << "fk " << hax2 << endl;
hax1[{hax2, hax3}]=ans+a1+a2+2+(d-2)*n;
} else
ans+=hax1[{hax2, hax3}];
}
cout << ans+d*n << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
25208 KB |
Output is correct |
2 |
Correct |
45 ms |
25444 KB |
Output is correct |
3 |
Correct |
68 ms |
25520 KB |
Output is correct |
4 |
Correct |
87 ms |
25520 KB |
Output is correct |
5 |
Correct |
74 ms |
25520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
29660 KB |
Output is correct |
2 |
Correct |
48 ms |
30352 KB |
Output is correct |
3 |
Correct |
80 ms |
30352 KB |
Output is correct |
4 |
Correct |
91 ms |
30352 KB |
Output is correct |
5 |
Correct |
73 ms |
30352 KB |
Output is correct |
6 |
Correct |
109 ms |
30352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
33784 KB |
Output is correct |
2 |
Correct |
63 ms |
38776 KB |
Output is correct |
3 |
Correct |
118 ms |
38776 KB |
Output is correct |
4 |
Correct |
92 ms |
38776 KB |
Output is correct |
5 |
Correct |
72 ms |
38776 KB |
Output is correct |
6 |
Correct |
409 ms |
38776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
571 ms |
38776 KB |
Output is correct |
2 |
Correct |
75 ms |
49500 KB |
Output is correct |
3 |
Correct |
140 ms |
49500 KB |
Output is correct |
4 |
Correct |
97 ms |
49500 KB |
Output is correct |
5 |
Correct |
83 ms |
49500 KB |
Output is correct |
6 |
Correct |
430 ms |
49500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1142 ms |
49500 KB |
Output is correct |
2 |
Correct |
248 ms |
55700 KB |
Output is correct |
3 |
Correct |
607 ms |
63608 KB |
Output is correct |
4 |
Correct |
241 ms |
63608 KB |
Output is correct |
5 |
Correct |
218 ms |
63608 KB |
Output is correct |
6 |
Correct |
564 ms |
63608 KB |
Output is correct |
7 |
Correct |
583 ms |
63608 KB |
Output is correct |