Submission #1867051
Source Code Expand
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
map<int,set<ii> > R;
map<int,set<ii> > C;
map<int,vector<int> > rows;
map<int,vector<int> > cols;
ii pt[111111];
ll ans;
int calcrow(int x, int l, int r)
{
if(rows.find(x)==rows.end()) return 0;
int lb = lower_bound(rows[x].begin(),rows[x].end(),l)-rows[x].begin();
int rb = lower_bound(rows[x].begin(),rows[x].end(),r+1)-rows[x].begin();
return rb-lb;
}
int calccol(int x, int l, int r)
{
if(cols.find(x)==cols.end()) return 0;
int lb = lower_bound(cols[x].begin(),cols[x].end(),l)-cols[x].begin();
int rb = lower_bound(cols[x].begin(),cols[x].end(),r+1)-cols[x].begin();
return rb-lb;
}
int d=0;
bool vis[111111];
void process(int u)
{
vis[u]=1;
int x=pt[u].fi; int y=pt[u].se;
ans+=calcrow(x-d,y-d,y+d);
ans+=calcrow(x+d,y-d,y+d);
ans+=calccol(y-d,x-d+1,x+d-1);
ans+=calccol(y+d,x-d+1,x+d-1);
vi Q;
if(!R[x-d].empty())
{
auto it = R[x-d].lower_bound(mp(y-d,-1));
while(it!=R[x-d].end())
{
if((*it).fi<=y+d)
{
Q.pb((*it).se);
C[(*it).se].erase(mp(x-d,(*it).se));
it=R[x-d].erase(it);
}
else break;
}
}
if(!R[x+d].empty())
{
auto it = R[x+d].lower_bound(mp(y-d,-1));
while(it!=R[x+d].end())
{
if((*it).fi<=y+d)
{
Q.pb((*it).se);
C[(*it).se].erase(mp(x+d,(*it).se));
it=R[x+d].erase(it);
}
else break;
}
}
if(!C[y+d].empty())
{
auto it = C[y+d].lower_bound(mp(x-d+1,-1));
while(it!=C[y+d].end())
{
if((*it).fi<=x+d-1)
{
Q.pb((*it).se);
R[(*it).se].erase(mp(y+d,(*it).se));
it=C[y+d].erase(it);
}
else break;
}
}
if(!C[y-d].empty())
{
auto it = C[y-d].lower_bound(mp(x-d+1,-1));
while(it!=C[y-d].end())
{
if((*it).fi<=x+d-1)
{
Q.pb((*it).se);
R[(*it).se].erase(mp(y-d,(*it).se));
it=C[y-d].erase(it);
}
else break;
}
}
for(int i=0;i<Q.size();i++)
{
if(!vis[Q[i]]) process(Q[i]);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n,s1,s2; cin>>n>>s1>>s2; s1--; s2--;
for(int i=0;i<n;i++)
{
int x,y; cin>>x>>y;
int px,py; px=x-y; py=x+y;
pt[i].fi=px; pt[i].se=py;
rows[px].pb(py); cols[py].pb(px);
if(i!=s1)
{
R[px].insert(mp(py,i)); C[py].insert(mp(px,i));
}
}
for(auto it = rows.begin(); it != rows.end(); it++)
{
sort(it->se.begin(), it->se.end());
}
for(auto it = cols.begin(); it != cols.end(); it++)
{
sort(it->se.begin(), it->se.end());
}
d=max(abs(pt[s1].fi-pt[s2].fi),abs(pt[s1].se-pt[s2].se));
process(s1);
ans>>=1;
assert(ans<=int(2e9));
cout<<ans<<'\n';
}
Submission Info
Submission Time |
|
Task |
E - Manhattan Compass |
User |
zscoder |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
3228 Byte |
Status |
RE |
Exec Time |
935 ms |
Memory |
103168 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt |
All |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_2.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_0.txt |
AC |
1 ms |
256 KB |
subtask0_1.txt |
AC |
1 ms |
256 KB |
subtask0_2.txt |
AC |
1 ms |
256 KB |
subtask1_0.txt |
RE |
381 ms |
56188 KB |
subtask1_1.txt |
RE |
376 ms |
55408 KB |
subtask1_10.txt |
AC |
863 ms |
59264 KB |
subtask1_11.txt |
AC |
99 ms |
12160 KB |
subtask1_12.txt |
AC |
175 ms |
30844 KB |
subtask1_13.txt |
AC |
174 ms |
30844 KB |
subtask1_14.txt |
AC |
935 ms |
89344 KB |
subtask1_15.txt |
AC |
101 ms |
12032 KB |
subtask1_16.txt |
RE |
400 ms |
58204 KB |
subtask1_17.txt |
RE |
397 ms |
57188 KB |
subtask1_18.txt |
AC |
485 ms |
30080 KB |
subtask1_19.txt |
AC |
102 ms |
12032 KB |
subtask1_2.txt |
AC |
854 ms |
103168 KB |
subtask1_20.txt |
AC |
399 ms |
58048 KB |
subtask1_21.txt |
AC |
366 ms |
58084 KB |
subtask1_22.txt |
AC |
482 ms |
32384 KB |
subtask1_23.txt |
AC |
516 ms |
41600 KB |
subtask1_24.txt |
RE |
391 ms |
58108 KB |
subtask1_3.txt |
AC |
283 ms |
24064 KB |
subtask1_4.txt |
AC |
374 ms |
57572 KB |
subtask1_5.txt |
AC |
352 ms |
57800 KB |
subtask1_6.txt |
AC |
552 ms |
34944 KB |
subtask1_7.txt |
AC |
302 ms |
26496 KB |
subtask1_8.txt |
AC |
181 ms |
30460 KB |
subtask1_9.txt |
AC |
359 ms |
57324 KB |