| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 949441 | MilosMilutinovic | IOI Fever (JOI21_fever) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
ll readint(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
#define int long long
#define info pair<pair<ll,int>,pair<ll,int>>
int n,tot;
int d1[400005],d2[400005],d3[400005],d4[400005],root[4][400005],lch[15000005],rch[15000005],pos[4][400005];
ll x[400005],y[400005],dir[400005];
bool vis[400005];
pair<ll,int> mn[15000005][4],mx[15000005][4];
void change(int&id,int t,int l,int r,int ql,int qr,info v){
if(!id) id=++tot,mn[id][t]=mp((ll)1e18,0),mx[id][t]=mp((ll)-1e18,0);
if(ql<=l&&r<=qr){
mn[id][t]=min(mn[id][t],v.fi);
mx[id][t]=max(mx[id][t],v.se);
return;
}
int mid=(l+r)/2;
if(qr<=mid) change(lch[id],t,l,mid,ql,qr,v);
else if(ql>mid) change(rch[id],t,mid+1,r,ql,qr,v);
else change(lch[id],t,l,mid,ql,qr,v),change(rch[id],t,mid+1,r,ql,qr,v);
}
pair<ll,int> query(int id,int t,int l,int r,int i,int v){
if(!id) return mp((ll)1e18,0);
if(l==r) return min(mp(mn[id][t].fi-v,mn[id][t].se),mp(v-mx[id][t].fi,mx[id][t].se));
int mid=(l+r)/2;
pair<ll,int> bst;
if(i<=mid) bst=query(lch[id],t,l,mid,i,v);
else bst=query(rch[id],t,mid+1,r,i,v);
bst=min(bst,min(mp(mn[id][t].fi-v,mn[id][t].se),mp(v-mx[id][t].fi,mx[id][t].se)));
return bst;
}
signed main(){
n=readint();
for(int i=1;i<=n;i++) x[i]=readint(),y[i]=readint(),x[i]*=2,y[i]*=2;
vector<int> xs1,xs2,xs3,xs4;
for(int i=1;i<=n;i++){
xs1.pb(x[i]+y[i]);
xs2.pb(x[i]-y[i]);
xs3.pb(x[i]);
xs4.pb(y[i]);
}
sort(xs1.begin(),xs1.end());
xs1.erase(unique(xs1.begin(),xs1.end()),xs1.end());
sort(xs2.begin(),xs2.end());
xs2.erase(unique(xs2.begin(),xs2.end()),xs2.end());
sort(xs3.begin(),xs3.end());
xs3.erase(unique(xs3.begin(),xs3.end()),xs3.end());
sort(xs4.begin(),xs4.end());
xs4.erase(unique(xs4.begin(),xs4.end()),xs4.end());
int sz1=(int)xs1.size(),sz2=(int)xs2.size(),sz3=(int)xs3.size(),sz4=(int)xs4.size();
vector<set<pii>> st1(sz1),st2(sz2),st3(sz3),st4(sz4);
vector<vector<int>> ids1(sz1),ids2(sz2),ids3(sz3),ids4(sz4);
for(int i=1;i<=n;i++){
d1[i]=(int)(lower_bound(xs1.begin(),xs1.end(),x[i]+y[i])-xs1.begin());
d2[i]=(int)(lower_bound(xs2.begin(),xs2.end(),x[i]-y[i])-xs2.begin());
d3[i]=(int)(lower_bound(xs3.begin(),xs3.end(),x[i])-xs3.begin());
d4[i]=(int)(lower_bound(xs4.begin(),xs4.end(),y[i])-xs4.begin());
st1[d1[i]].emplace(x[i],i);
st2[d2[i]].emplace(x[i],i);
st3[d3[i]].emplace(y[i],i);
st4[d4[i]].emplace(x[i],i);
ids1[d1[i]].pb(i);
ids2[d2[i]].pb(i);
ids3[d3[i]].pb(i);
ids4[d4[i]].pb(i);
}
for(int i=0;i<sz1;i++){
sort(ids1[i].begin(),ids1[i].end(),[&](int i,int j){return x[i]<x[j];});
for(int j=0;j<(int)ids1[i].size();j++){
pos[0][ids1[i][j]]=j;
}
}
for(int i=0;i<sz2;i++){
sort(ids2[i].begin(),ids2[i].end(),[&](int i,int j){return x[i]<x[j];});
for(int j=0;j<(int)ids2[i].size();j++){
pos[1][ids2[i][j]]=j;
}
}
for(int i=0;i<sz3;i++){
sort(ids3[i].begin(),ids3[i].end(),[&](int i,int j){return y[i]<y[j];});
for(int j=0;j<(int)ids3[i].size();j++){
pos[2][ids3[i][j]]=j;
}
}
for(int i=0;i<sz4;i++){
sort(ids4[i].begin(),ids4[i].end(),[&](int i,int j){return x[i]<x[j];});
for(int j=0;j<(int)ids4[i].size();j++){
pos[3][ids4[i][j]]=j;
}
}
int ans=0;
for(int d=0;d<4;d++){
for(int i=1;i<=n;i++) vis[i]=false;
dir[1]=d;
priority_queue<pair<ll,pii>> pq;
pq.push(mp(0,mp(1,d)));
for(int i=1;i<=n;i++){
st1[d1[i]].emplace(x[i],i);
st2[d2[i]].emplace(x[i],i);
st3[d3[i]].emplace(y[i],i);
st4[d4[i]].emplace(x[i],i);
}
while(tot){
for(int j=0;j<4;j++){
mn[tot][j]=mp((ll)1e18,0);
mx[tot][j]=mp((ll)-1e18,0);
}
lch[tot]=0;
rch[tot]=0;
tot--;
}
for(int j=0;j<4;j++){
for(int i=0;i<sz1;i++) root[j][i]=0;
for(int i=0;i<sz2;i++) root[j][i]=0;
}
auto upd=[&](int idx){
if(vis[idx]) return;
pair<ll,int> bst=min(query(root[0][d1[idx]],0,0,ids1[d1[idx]].size()-1,pos[0][idx],x[idx]),query(root[1][d2[idx]],1,0,ids2[d2[idx]].size()-1,pos[1][idx],x[idx]));
bst=min({bst,query(root[2][d3[idx]],2,0,ids3[d3[idx]].size()-1,pos[2][idx],y[idx]/2),query(root[3][d4[idx]],3,0,ids4[d4[idx]].size()-1,pos[3][idx],x[idx]/2)});
if(bst.fi<(ll)1e17){
pq.push(mp(-bst.fi,mp(idx,bst.se)));
}
return;
};
while(!pq.empty()){
ll t=-pq.top().fi;
int i=pq.top().se.fi;
int dd=pq.top().se.se;
pq.pop();
if(vis[i]) continue;
dir[i]=dd;
vis[i]=true;
auto it1=st1[d1[i]].lower_bound(mp(x[i],i));
if(it1!=st1[d1[i]].begin()) upd(prev(it1)->se);
if(it1!=prev(st1[d1[i]].end())) upd(next(it1)->se);
st1[d1[i]].erase(it1);
auto it2=st2[d2[i]].lower_bound(mp(x[i],i));
if(it2!=st2[d2[i]].begin()) upd(prev(it2)->se);
if(it2!=prev(st2[d2[i]].end())) upd(next(it2)->se);
st2[d2[i]].erase(it2);
auto it3=st3[d3[i]].lower_bound(mp(y[i],i));
if(it3!=st3[d3[i]].begin()) upd(prev(it3)->se);
if(it3!=prev(st3[d3[i]].end())) upd(next(it3)->se);
st3[d3[i]].erase(it3);
auto it4=st4[d4[i]].lower_bound(mp(x[i],i));
if(it4!=st4[d4[i]].begin()) upd(prev(it4)->se);
if(it4!=prev(st4[d4[i]].end())) upd(next(it4)->se);
st4[d4[i]].erase(it4);
if(dir[i]==0){
// up
{
int low=0,high=ids1[d1[i]].size()-1,p=-1;
while(low<=high){
int mid=(low+high)/2;
if(x[i]-x[ids1[d1[i]][mid]]>=t) p=mid,low=mid+1;
else high=mid-1;
}
if(p!=-1){
change(root[0][d1[i]],0,0,ids1[d1[i]].size()-1,0,p,mp(mp(x[i],2),mp((ll)-1e18,0)));
auto it=st1[d1[i]].lower_bound(mp(x[ids1[d1[i]][p]],ids1[d1[i]][p]+1));
if(it!=st1[d1[i]].begin()) upd(prev(it)->se);
}
}
{
int low=0,high=ids2[d2[i]].size()-1,p=high+1;
while(low<=high){
int mid=(low+high)/2;
if(x[ids2[d2[i]][mid]]-x[i]>=t) p=mid,high=mid-1;
else low=mid+1;
}
if(p<(int)ids2[d2[i]].size()){
change(root[1][d2[i]],1,0,ids2[d2[i]].size()-1,p,ids2[d2[i]].size()-1,mp(mp((ll)1e18,0),mp(x[i],3)));
auto it=st2[d2[i]].lower_bound(mp(x[ids2[d2[i]][p]],ids2[d2[i]][p]));
if(it!=st2[d2[i]].end()) upd(it->se);
}
}
{
int low=0,high=ids3[d3[i]].size()-1,p=high+1;
while(low<=high){
int mid=(low+high)/2;
if((y[ids3[d3[i]][mid]]-y[i])/2>=t) p=mid,high=mid-1;
else low=mid+1;
}
if(p<ids3[d3[i]].size()){
change(root[2][d3[i]],2,0,ids3[d3[i]].size()-1,p,ids3[d3[i]].size()-1,mp(mp((ll)1e18,0),mp(y[i]/2,1)));
auto it=st3[d3[i]].lower_bound(mp(y[ids3[d3[i]][p]],ids3[d3[i]][p]));
if(it!=st3[d3[i]].end()) upd(it->se);
}
}
}
if(dir[i]==1){
// down
{
int low=0,high=ids1[d1[i]].size()-1,p=high+1;
while(low<=high){
int mid=(low+high)/2;
if(x[ids1[d1[i]][mid]]-x[i]>=t) p=mid,high=mid-1;
else low=mid+1;
}
if(p<(int)ids1[d1[i]].size()){
change(root[0][d1[i]],0,0,ids1[d1[i]].size()-1,p,ids1[d1[i]].size()-1,mp(mp((ll)1e18,2),mp(x[i],3)));
auto it=st1[d1[i]].lower_bound(mp(x[ids1[d1[i]][p]],ids1[d1[i]][p]));
if(it!=st1[d1[i]].end()) upd(it->se);
}
}
{
int low=0,high=ids2[d2[i]].size()-1,p=-1;
while(low<=high){
int mid=(low+high)/2;
if(x[i]-x[ids2[d2[i]][mid]]>=t) p=mid,low=mid+1;
else high=mid-1;
}
if(p!=-1){
change(root[1][d2[i]],1,0,ids2[d2[i]].size()-1,0,p,mp(mp(x[i],2),mp((ll)-1e18,3)));
auto it=st2[d2[i]].lower_bound(mp(x[ids2[d2[i]][p]],ids2[d2[i]][p]+1));
if(it!=st2[d2[i]].begin()) upd(prev(it)->se);
}
}
{
int low=0,high=ids3[d3[i]].size()-1,p=-1;
while(low<=high){
int mid=(low+high)/2;
if((y[i]-y[ids3[d3[i]][mid]])/2>=t) p=mid,low=mid+1;
else high=mid-1;
}
if(p!=-1){
change(root[2][d3[i]],2,0,ids3[d3[i]].size()-1,0,p,mp(mp(y[i]/2,0),mp(-(ll)1e18,1)));
auto it=st3[d3[i]].lower_bound(mp(y[ids3[d3[i]][p]],ids3[d3[i]][p]+1));
if(it!=st3[d3[i]].begin()) upd(prev(it)->se);
}
}
}
if(dir[i]==2){
// right
{
int low=0,high=ids1[d1[i]].size()-1,p=high+1;
while(low<=high){
int mid=(low+high)/2;
if(x[ids1[d1[i]][mid]]-x[i]>=t) p=mid,high=mid-1;
else low=mid+1;
}
if(p<(int)ids1[d1[i]].size()){
change(root[0][d1[i]],0,0,ids1[d1[i]].size()-1,p,ids1[d1[i]].size()-1,mp(mp((ll)1e18,2),mp(x[i],0)));
auto it=st1[d1[i]].lower_bound(mp(x[ids1[d1[i]][p]],ids1[d1[i]][p]));
if(it!=st1[d1[i]].end()) upd(it->se);
}
}
{
int low=0,high=ids2[d2[i]].size()-1,p=high+1;
while(low<=high){
int mid=(low+high)/2;
if(x[ids2[d2[i]][mid]]-x[i]>=t) p=mid,high=mid-1;
else low=mid+1;
}
if(p<(int)ids2[d2[i]].size()){
change(root[1][d2[i]],1,0,ids2[d2[i]].size()-1,p,ids2[d2[i]].size()-1,mp(mp((ll)1e18,0),mp(x[i],1)));
auto it=st2[d2[i]].lower_bound(mp(x[ids2[d2[i]][p]],ids2[d2[i]][p]));
if(it!=st2[d2[i]].end()) upd(it->se);
}
}
{
int low=0,high=ids4[d4[i]].size()-1,p=high+1;
while(low<=high){
int mid=(low+high)/2;
if((x[ids4[d4[i]][mid]]-x[i])/2>=t) p=mid,high=mid-1;
else low=mid+1;
}
if(p<ids4[d4[i]].size()){
change(root[3][d4[i]],3,0,ids4[d4[i]].size()-1,p,ids4[d4[i]].size()-1,mp(mp((ll)1e18,0),mp(x[i]/2,3)));
auto it=st4[d4[i]].lower_bound(mp(x[ids4[d4[i]][p]],ids4[d4[i]][p]));
if(it!=st4[d4[i]].end()) upd(it->se);
}
}
}
if(dir[i]==3){
// left
{
int low=0,high=ids1[d1[i]].size()-1,p=-1;
while(low<=high){
int mid=(low+high)/2;
if(x[i]-x[ids1[d1[i]][mid]]>=t) p=mid,low=mid+1;
else high=mid-1;
}
if(p!=-1){
change(root[0][d1[i]],0,0,ids1[d1[i]].size()-1,0,p,mp(mp(x[i],1),mp((ll)-1e18,0)));
auto it=st1[d1[i]].lower_bound(mp(x[ids1[d1[i]][p]],ids1[d1[i]][p]+1));
if(it!=st1[d1[i]].begin()) upd(prev(it)->se);
}
}
{
int low=0,high=ids2[d2[i]].size()-1,p=-1;
while(low<=high){
int mid=(low+high)/2;
if(x[i]-x[ids2[d2[i]][mid]]>=t) p=mid,low=mid+1;
else high=mid-1;
}
if(p!=-1){
change(root[1][d2[i]],1,0,ids2[d2[i]].size()-1,0,p,mp(mp(x[i],0),mp((ll)-1e18,3)));
auto it=st2[d2[i]].lower_bound(mp(x[ids2[d2[i]][p]],ids2[d2[i]][p]+1));
if(it!=st2[d2[i]].begin()) upd(prev(it)->se);
}
}
{
int low=0,high=ids4[d4[i]].size()-1,p=-1;
while(low<=high){
int mid=(low+high)/2;
if((x[i]-x[ids4[d4[i]][mid]])/2>=t) p=mid,low=mid+1;
else high=mid-1;
}
if(p!=-1){
change(root[3][d4[i]],3,0,ids4[d4[i]].size()-1,0,p,mp(mp(x[i]/2,2),mp((ll)-1e18,3)));
auto it=st4[d4[i]].lower_bound(mp(x[ids4[d4[i]][p]],ids4[d4[i]][p]+1));
if(it!=st4[d4[i]].begin()) upd(prev(it)->se);
}
}
}
}
int cnt=0;
for(int i=1;i<=n;i++) cnt+=vis[i];
ans=max(ans,cnt);
}
printf("%d\n",ans);
}