Submission #1094151

#TimeUsernameProblemLanguageResultExecution timeMemory
1094151modwweRoad Construction (JOI21_road_construction)C++17
0 / 100
3016 ms18916 KiB
//https://www.instagram.com/_modwwe/ #pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("avx2,bmi,bmi2") #include<bits/stdc++.h> //#define int long long //#define ll long long #define down cout<<'\n'; #define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); #define modwwe int t;cin>>t; while(t--) #define bit(i,j) (i>>j&1) #define sobit(a) __builtin_popcountll(a) #define task "test" #define fin(x) freopen(x".inp","r",stdin) #define fou(x) freopen(x".out","w",stdout) #define pb push_back #define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; using namespace std; void phongbeo(); const int inf=1e18; const int mod2=1e9+7; const int mod1=998244353; struct icd { int a,b; }; struct ib { int a; int b; }; struct ic { int a,b,c; }; struct id { int a,b,c,d; }; struct ie { int a,b,c, d,e,f; }; int n,m,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l; int i,s10,s12; int el=29; main() { #ifndef ONLINE_JUDGE /// fin(task),fou(task); #endif NHP; /// cin>>s1; // modwwe phongbeo(),down } int d[250001]; struct IT { ib t[1000001]; void build(int node,int l,int r) { t[node]= {inf,0}; if(l==r) return; int mid=l+r>>1; build(node<<1,l,mid); build(node<<1|1,mid+1,r); } ib mer(ib a,ib b) { if(a.a<b.a) return a; return b; } void upd(int node,int l,int r,int l1,int x) { if(l==r) { t[node]= {x,l}; return; } int mid=l+r>>1; if(l1<=mid)upd(node<<1,l,mid,l1,x); else upd(node<<1|1,mid+1,r,l1,x); t[node]=mer(t[node<<1],t[node<<1|1]); } ib get(int node,int l,int r,int l1,int r1 ) { if(l1>r1) return {inf,0}; if(l>r1||r<l1) return {inf,0}; if(l>=l1&&r<=r1)return t[node]; int mid=l+r>>1; return mer(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1)); } } st1,st2; ib sx; ib a[250001]; bool check(int f) { dem=0; st1.build(1,1,n); st2.build(1,1,n); for(int i=n; i>=1; --i) { stack<ic> s; /// cot be hon sx=st1.get(1,1,n,1,a[i].b-1); s3=d[a[i].b]; if(sx.a-a[i].a+s3<=f) s.push({1,a[i].b-1,sx.b}),dem++; while(!s.empty()) { if(dem>=m) return 1; ic x=s.top(); s.pop(); sx=st1.get(1,1,n,x.a,x.c-1); if(sx.a-a[i].a+s3<=f)dem++,s.push({x.a,x.c-1,sx.b}); sx=st1.get(1,1,n,x.c+1,x.b); if(sx.a-a[i].a+s3<=f)dem++,s.push({x.c+1,x.b,sx.b}); } if(dem>=m) return 1; sx=st2.get(1,1,n,a[i].b+1,n); if(sx.a-a[i].a-s3<=f) s.push({a[i].b+1,n,sx.b}),dem++; while(!s.empty()) { if(dem>=m) return 1; ic x=s.top(); s.pop(); sx=st2.get(1,1,n,x.a,x.c-1); if(sx.a-a[i].a-s3<=f) dem++,s.push({x.a,x.c-1,sx.b}); sx=st2.get(1,1,n,x.c+1,x.b); if(sx.a-a[i].a-s3<=f)dem++,s.push({x.c+1,x.b,sx.b}); } if(dem>=m) return 1; st1.upd(1,1,n,a[i].b,a[i].a-s3); st2.upd(1,1,n,a[i].b,a[i].a+s3); } if(dem>=m) return 1; return 0; } vector<int> v; void answer(int f) { dem=0; st1.build(1,1,n); st2.build(1,1,n); for(int i=n; i>=1; --i) { stack<ic> s; sx=st1.get(1,1,n,1,a[i].b-1); s3=d[a[i].b]; while(!s.empty()) s.pop(); if(sx.a-a[i].a+s3<f){ s.push({1,a[i].b-1,sx.b}),dem++,v.pb(sx.a-a[i].a+s3); } while(!s.empty()) { if(dem>=m) break; ic x=s.top(); s.pop(); sx=st1.get(1,1,n,x.a,x.c-1); if(sx.a-a[i].a+s3<f)dem++,s.push({x.a,x.c-1,sx.b}),v.pb(sx.a-a[i].a+s3); sx=st1.get(1,1,n,x.c+1,x.b); if(sx.a-a[i].a+s3<f)dem++,s.push({x.c+1,x.b,sx.b}),v.pb(sx.a-a[i].a+s3); } if(dem>=m)break; sx=st2.get(1,1,n,a[i].b+1,n); while(!s.empty()) s.pop(); if(sx.a-a[i].a-s3<f){ s.push({a[i].b+1,n,sx.b}),dem++,v.pb(sx.a-a[i].a-s3); // cout<<sx.a-a[i].a-s3<<" "<<i<<" "<<sx.a,down } while(!s.empty()) { if(dem>=m) break; ic x=s.top(); s.pop(); sx=st2.get(1,1,n,x.a,x.c-1); if(sx.a-a[i].a-s3<f) dem++,s.push({x.a,x.c-1,sx.b}),v.pb(sx.a-a[i].a-s3); sx=st2.get(1,1,n,x.c+1,x.b); if(sx.a-a[i].a-s3<f)dem++,s.push({x.c+1,x.b,sx.b}),v.pb(sx.a-a[i].a-s3); } if(dem>=m) break; st1.upd(1,1,n,a[i].b,a[i].a-s3); st2.upd(1,1,n,a[i].b,a[i].a+s3); } sort(v.begin(),v.end()); for(int i=m-v.size();i>=0;--i) v.pb(f); for(int i=0; i<m; i++) cout<<v[i],down } bool cmp2(ib x,ib y) { return x.b<y.b; } bool cmp(ib a,ib b) { return a.a<b.a; } void phongbeo() { cin>>n>>m; for(int i=1; i<=n; i++) cin>>a[i].a>>a[i].b; sort(a+1,a+1+n,cmp2); for(int i=1; i<=n; i++) d[i]=a[i].b, a[i].b=i; sort(a+1,a+1+n,cmp); l=0; r=4e9; while(l<=r) { int mid=l+r>>1; if(check(mid)) { mx=mid; r=mid-1; } else l=mid+1; } answer(mx); }

Compilation message (stderr)

road_construction.cpp:19:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int inf=1e18;
      |               ^~~~
road_construction.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main()
      | ^~~~
road_construction.cpp: In member function 'void IT::build(int, int, int)':
road_construction.cpp:65:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid=l+r>>1;
      |                 ~^~
road_construction.cpp: In member function 'void IT::upd(int, int, int, int, int)':
road_construction.cpp:81:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         int mid=l+r>>1;
      |                 ~^~
road_construction.cpp: In member function 'ib IT::get(int, int, int, int, int)':
road_construction.cpp:91:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         int mid=l+r>>1;
      |                 ~^~
road_construction.cpp: In function 'void phongbeo()':
road_construction.cpp:215:7: warning: overflow in conversion from 'double' to 'int' changes value from '4.0e+9' to '2147483647' [-Woverflow]
  215 |     r=4e9;
      |       ^~~
road_construction.cpp:218:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  218 |         int mid=l+r>>1;
      |                 ~^~
#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...