제출 #47904

#제출 시각아이디문제언어결과실행 시간메모리
47904temurbek_khujaevGap (APIO16_gap)C++17
68.05 / 100
117 ms20856 KiB
#include <bits/stdc++.h> #include "gap.h" using namespace std; typedef long long ll; ll v[223456]; #define fi first #define se second void upmax(ll &x,ll y) { x=max(x,y); } long long findGap(int T, int n) { ll ans=0; if (T==1) { int l=0, r=n-1; MinMax(0ll,(1ll<<60),&v[0],&v[n-1]); for (int i=0;i<n/2;i++) { if (l+1==r) break; MinMax(v[l]+1,v[r]-1,&v[l+1],&v[r-1]); l++; r--; } for (int i=1;i<n;i++) { ans=max(ans,v[i]-v[i-1]); } return ans; } else { ll L,R; MinMax(0ll,(1ll<<60),&L,&R); set<pair<ll,pair<ll,ll> > > s; s.insert({L-R,{L,R}}); ll lf=0,rg; do { ll d=-s.begin()->fi; if (d<=ans) { // cout<<ans<<endl; return ans; } ll x=s.begin()->se.fi; ll y=s.begin()->se.se; s.erase(s.begin()); ll f=d/3; ll m1,m2; //cout<< x << ' ' << y <<'\t'<<ans<<endl; MinMax(x+f,x+f+f,&m1,&m2); //cout<<m1<<' '<<m2<<endl; if (m1==-1) { ll mn1,mx1,mn2,mx2; if (x+1>x+f-1) mn1=mx1=-1; else MinMax(x+1,x+f-1,&mn1,&mx1); if (x+2*f+1>y-1) mn2=mx2=-1; else MinMax(x+2*f+1,y-1,&mn2,&mx2); //cout<<' '<<mn1<<' '<<mn2<<endl; if (mn1==-1&&mn2==-1){ // cout<<max(ans,d)<<endl; return max(ans,d); } else { if (mx1!=-1&&mn2!=-1) upmax(ans,mn2-mx1); if(mn1==-1) { upmax(ans,mn2-x); } else { upmax(ans,mn1-x); s.insert({mn1-mx1,{mn1,mx1}}); if (mn2!=-1) s.insert({mx1-mn2,{mn1,mn2}}); } if(mn2==-1) { upmax(ans,y-mx1); } else { upmax(ans,y-mx2); s.insert({mn2-mx2,{mn2,mx2}}); } } } else { s.insert({x-m1,{x,m1}}); s.insert({m2-y,{m2,y}}); if (m1 != m2) s.insert({m1-m2,{m1,m2}}); } } while (!s.empty()); } //cout<<"ANS="<<ans<<endl; return ans; }

컴파일 시 표준 에러 (stderr) 메시지

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:40:16: warning: unused variable 'lf' [-Wunused-variable]
             ll lf=0,rg;
                ^~
gap.cpp:40:21: warning: unused variable 'rg' [-Wunused-variable]
             ll lf=0,rg;
                     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...