Submission #522635

#TimeUsernameProblemLanguageResultExecution timeMemory
522635nathanlee726Road Construction (JOI21_road_construction)C++14
100 / 100
9510 ms95656 KiB
//#include<i_am_noob_orz> #include<bits/stdc++.h> #pragma GCC optimize(2) #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #define ll long long #define int ll #define ull unsigned long long #define pii pair<int,int> #define X first #define Y second #define mod ((ll)1e9+7) #define pb push_back #define mp make_pair #define abs(x) ((x)>0?(x):(-(x))) #define F(n) Fi(i,n) #define Fi(i,n) Fl(i,0,n) #define Fl(i,l,n) for(int i=l;i<n;i++) #define memres(a) memset(a,0,sizeof(a)) #define all(a) a.begin(),a.end() #define sz(a) ((int)a.size()) #define ceiling(a,b) (((a)+(b)-1)/(b)) #define endl '\n' #define bit_count(x) __builtin_popcountll((x)) #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define jimmy_is_kind false typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree; //#undef LOCAL //#define LOCAL #ifdef LOCAL #define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__) template<typename T> void _do(T && x) {cerr<<x<<endl;} template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);} #define IOS() #else #define IOS() ios_base::sync_with_stdio(0), cin.tie(0) #define endl '\n' #define bug(...) #endif int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);} int sub(int a,int b){return(a<b?a+mod-b:a-b);} int po(int a,int b){ if(b==0)return 1; if(b==1)return(a%mod); int tem=po(a,b/2); if(b&1)return(((tem*tem)%mod)*a)%mod; else return(tem*tem)%mod; } int GCD(int a,int b){ int x=0; int ra,rb; while(a&&b){ if(((a&1)==0)&&((b&1)==0)){ a>>=1,b>>=1,x++; } else if((a^b)&1){ if(a&1)b>>=1; else a>>=1; } else{ ra=abs(a-b),rb=min(a,b); a=ra,b=rb; } } return max(a,b)<<x; } int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);} int n,k,ind=0,rd[250010]; pii pt[250010]; multiset<signed> st[250010]; struct TREAP{ int l,r,pr,v,c,si; TREAP():l(-1),r(-1),pr(-1),v(-1),c(0),si(0){} }treap[250010],treap1[250010]; void pull(int p){ int ss=treap[p].c; if(treap[p].l!=-1)ss+=treap[treap[p].l].si; if(treap[p].r!=-1)ss+=treap[treap[p].r].si; treap[p].si=ss; } int merge(int a,int b){ if(a==-1||b==-1){ if(a==-1)return b; else return a; } if(treap[a].pr>treap[b].pr){ treap[a].r=merge(treap[a].r,b); pull(a); return a; } else{ treap[b].l=merge(a,treap[b].l); pull(b); return b; } } pii split(int a,int x){ if(a==-1)return{-1,-1}; if(treap[a].v<=x){ pii tp=split(treap[a].r,x); treap[a].r=tp.X; pull(a); return {a,tp.Y}; } else{ pii tp=split(treap[a].l,x); treap[a].l=tp.Y; pull(a); return {tp.X,a}; } } int insert(int a,int x){ if(a==-1){ treap[ind].v=x; treap[ind].c=treap[ind].si=1; treap[ind].pr=rd[ind]; int pp=ind++; return pp; } pii pt1=split(a,x); pii pt2=split(pt1.X,x-1); if(pt2.Y!=-1){ treap[pt2.Y].c++; treap[pt2.Y].si=treap[pt2.Y].c; return merge(merge(pt2.X,pt2.Y),pt1.Y); } else{ treap[ind].v=x; treap[ind].c=treap[ind].si=1; treap[ind].pr=rd[ind]; int re=merge(merge(pt2.X,ind),pt1.Y); ind++; return re; } } int remove(int a,int x){ //bug(a,x); pii pt1=split(a,x); pii pt2=split(pt1.X,x-1); if(treap[pt2.Y].si==1){ treap[pt2.Y].si--; treap[pt2.Y].c--; return merge(pt2.X,pt1.Y); } else{ //assert(treap[pt2.Y].si>1); treap[pt2.Y].si--; treap[pt2.Y].c--; return merge(merge(pt2.X,pt2.Y),pt1.Y); } } int getv(int a,int x){ if(a==-1)return 0; int sl=(treap[a].l==-1?0:treap[treap[a].l].si); if(x>=treap[a].v)return getv(treap[a].r,x)+sl+treap[a].c; else return getv(treap[a].l,x); } //////// vector<pii> v; void pull1(int p){ int ss=treap1[p].c; if(treap1[p].l!=-1)ss+=treap1[treap[p].l].si; if(treap1[p].r!=-1)ss+=treap1[treap[p].r].si; treap1[p].si=ss; } int merge1(int a,int b){ if(a==-1||b==-1){ if(a==-1)return b; else return a; } if(treap1[a].pr>treap1[b].pr){ treap1[a].r=merge1(treap1[a].r,b); pull1(a); return a; } else{ treap1[b].l=merge1(a,treap1[b].l); pull1(b); return b; } } pii split1(int a,int x){ if(a==-1)return{-1,-1}; if(treap1[a].v<=x){ pii tp=split1(treap1[a].r,x); treap1[a].r=tp.X; pull1(a); return {a,tp.Y}; } else{ pii tp=split1(treap1[a].l,x); treap1[a].l=tp.Y; pull1(a); return {tp.X,a}; } } int insert1(int a,int x,int rx){ if(a==-1){ treap1[ind].v=x; treap1[ind].c=treap1[ind].si=1; treap1[ind].pr=rd[ind]; st[ind].insert(rx); int pp=ind++; return pp; } pii pt1=split1(a,x); pii pt2=split1(pt1.X,x-1); if(pt2.Y!=-1){ treap1[pt2.Y].c++; treap1[pt2.Y].si=treap1[pt2.Y].c; st[pt2.Y].insert(rx); return merge1(merge1(pt2.X,pt2.Y),pt1.Y); } else{ treap1[ind].v=x; treap1[ind].c=treap1[ind].si=1; treap1[ind].pr=rd[ind]; st[ind].insert(rx); int re=merge1(merge1(pt2.X,ind),pt1.Y); ind++; return re; } } int remove1(int a,int x,int rx){ pii pt1=split1(a,x); pii pt2=split1(pt1.X,x-1); if(treap1[pt2.Y].si==1){ treap1[pt2.Y].c--; treap1[pt2.Y].si--; st[pt2.Y].erase(st[pt2.Y].find(rx)); return merge1(pt2.X,pt1.Y); } else{ assert(treap1[pt2.Y].si>1); treap1[pt2.Y].si--; treap1[pt2.Y].c--; st[pt2.Y].erase(st[pt2.Y].find(rx)); return merge1(merge1(pt2.X,pt2.Y),pt1.Y); } } void travel(int a){ if(a==-1)return; travel(treap1[a].l); //bug(treap1[a].v,treap1[a].c,sz(st[a])); for(int i:st[a]){ v.pb({i,treap1[a].v}); } travel(treap1[a].r); } //////// signed main(){ IOS(); //freopen("05-01.txt","r",stdin); cin>>n>>k; F(n){ int x,y; cin>>x>>y; int xx,yy; xx=x+y; yy=x-y; pt[i]={xx,yy}; } sort(pt,pt+n); F(250005)rd[i]=i; random_shuffle(rd,rd+250004); int rt=-1; int l=0,r=4e9; queue<pii> qu; while(l<r){ int mi=(l+r)/2; int s=0; rt=-1,ind=0; F(n){ while(!qu.empty()){ if(qu.front().X>=pt[i].X-mi)break; rt=remove(rt,qu.front().Y); qu.pop(); } if(rt!=-1){ s+=getv(rt,pt[i].Y+mi)-getv(rt,pt[i].Y-mi-1); //bug(treap[ppt1.Y].si,ppt1.Y); } rt=insert(rt,pt[i].Y); qu.push(pt[i]); } //bug(mi,s); while(!qu.empty()){ rt=remove(rt,qu.front().Y); qu.pop(); } if(s<k)l=mi+1; else r=mi; } int tk=l; ind=0; rt=-1; while(!qu.empty())qu.pop(); multiset<int> sst; F(n){ while(!qu.empty()){ if(qu.front().X>=pt[i].X-tk)break; rt=remove1(rt,qu.front().Y,qu.front().X); qu.pop(); } if(rt!=-1){ pii ppt=split1(rt,pt[i].Y+tk); pii ppt1=split1(ppt.X,pt[i].Y-tk-1); v.clear(); travel(ppt1.Y); //assert(sz(v)==treap1[ppt1.Y].si); //bug(sz(v),treap1[ppt1.Y].si); for(pii pi:v){ sst.insert(max(abs(pi.X-pt[i].X),abs(pi.Y-pt[i].Y))); } rt=merge1(merge1(ppt1.X,ppt1.Y),ppt.Y); } rt=insert1(rt,pt[i].Y,pt[i].X); qu.push(pt[i]); } bug(tk); //F(n)bug(pt[i].X,pt[i].Y); int cc=0; for(int i:sst){ cc++; cout<<i<<endl; if(cc==k)break; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...