Submission #1214143

#TimeUsernameProblemLanguageResultExecution timeMemory
1214143user736482Radio Towers (IOI22_towers)C++20
11 / 100
1165 ms399836 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pb push_back #define ff first #define ss second #define MOD 1000000009 #define INF 1000000019 #define POT (1<<20) #define INFL 1000000000000000099 ll val[POT*3][5],lw[POT*3][5],pw[POT*3][5];//0 sum,1 min,2 min(na ujemnych) ll ak[5]; ll h[100007][17]; ll p1[100007],p2[100007]; ll pop[100007],nxt[100007]; vector<pair<ll,ll>>root[3];// <moment,nowy root> void st(ll cop,ll v,ll vl,ll idx,ll l,ll r,ll gdz){ lw[v][idx]=lw[cop][idx]; pw[v][idx]=pw[cop][idx]; if((l+r)/2>=gdz){ lw[v][idx]=ak[idx]; } else pw[v][idx]=ak[idx]; ak[idx]++; if(l==r){ val[v][idx]=vl; } else{ if((l+r)/2>=gdz)st(lw[cop][idx],lw[v][idx],vl,idx,l,(l+r)/2,gdz); else st(pw[cop][idx],pw[v][idx],vl,idx,(l+r)/2+1,r,gdz); if(idx) val[v][idx]=min(val[lw[v][idx]][idx],val[pw[v][idx]][idx]); else val[v][idx]=val[lw[v][idx]][idx]+val[pw[v][idx]][idx]; } } ll get(ll v,ll l,ll r,ll pocz,ll kon,ll idx){ if(pocz > r || kon < l)return idx*INFL; if(pocz<=l && kon>=r)return val[v][idx]; if(idx)return min(get(lw[v][idx],l,(l+r)/2,pocz,kon,idx),get(pw[v][idx],(l+r)/2+1,r,pocz,kon,idx)); else return get(lw[v][idx],l,(l+r)/2,pocz,kon,idx)+get(pw[v][idx],(l+r)/2+1,r,pocz,kon,idx); } ll mx(ll pocz,ll kon){ if(pocz>kon)return 0; ll lg=log2(kon-pocz+1); return max(h[pocz][lg],h[kon-(1<<lg)+1][lg]); } void init(int n,vector<int>H){ root[0].pb({INFL,0}); root[1].pb({INFL,0}); root[2].pb({INFL,0}); ak[0]=20;ak[1]=20;ak[2]=20; for(ll i=0;i<n;i++)h[i][0]=H[i]; for(ll i=0;i<20;i++){ for(ll idx=0;i<5;i++){ lw[i][idx]=i+1; pw[i][idx]=i+1; } } for(ll i=0;i<3*POT;i++){ for(ll j=1;j<5;j++)val[i][j]=INFL; } stack<pair<ll,ll>>stt; stt.push({-1,-1}); for(ll i=0;i<n;i++){ while(h[i][0]<=stt.top().ff)stt.pop(); pop[i]=stt.top().ss; stt.push({h[i][0],i}); } while(stt.size()>1)stt.pop(); stt.top().ss=n; for(ll i=n-1;i>=0;i--){ while(h[i][0]<=stt.top().ff)stt.pop(); nxt[i]=stt.top().ss; stt.push({h[i][0],i}); } for(ll j=1;j<17;j++){ for(ll i=0;i+(1<<j)<=n;i++)h[i][j]=max(h[i][j-1],h[i+(1<<(j-1))][j-1]); } vector<pair<ll,ll>>zd;//<czas,kto> for(ll i=0;i<n;i++){ p1[i]=mx(pop[i]+1,i-1)-h[i][0]; p2[i]=mx(i+1,nxt[i]-1)-h[i][0]; zd.pb({min(p1[i],p2[i]),-i-INFL}); if(p1[i]>p2[i]){ zd.pb({p1[i],-i-1}); } else zd.pb({p2[i],i}); } sort(zd.begin(),zd.end()); reverse(zd.begin(),zd.end()); for(auto op :zd){ if(op.ss<=-INFL){ ll i=-op.ss-INFL; root[0].pb({op.ff,ak[0]}); st(root[0][root[0].size()-2].ss,ak[0]++,1,0,1,POT/2,i+1); st(root[0][root[0].size()-2].ss,ak[3]++,i+1,3,1,POT/2,i+1); st(root[0][root[0].size()-2].ss,ak[4]++,-i-1,4,1,POT/2,i+1); if(p1[i]>p2[i]){ root[1].pb({op.ff,ak[1]}); st(root[1][root[1].size()-2].ss,ak[1]++,INFL,1,1,POT/2,i+1); } else{ root[2].pb({op.ff,ak[2]}); st(root[2][root[2].size()-2].ss,ak[2]++,INFL,2,1,POT/2,i+1); } } else if(op.ss<0){ ll i=-op.ss-1; root[1].pb({op.ff,ak[1]}); st(root[1][root[1].size()-2].ss,ak[1]++,-nxt[i]-1,1,1,POT/2,i+1); } else{ ll i=op.ss; root[2].pb({op.ff,ak[2]}); st(root[2][root[2].size()-2].ss,ak[2]++,pop[i]+1,2,1,POT/2,i+1); } } for(ll i=0;i<3;i++)reverse(root[i].begin(),root[i].end()); } ll max_towers(int l,int r,int d){ l++; r++; ll r0=(*lower_bound(root[0].begin(),root[0].end(),pair<ll,ll>{d,-INFL})).ss; ll r1=(*lower_bound(root[1].begin(),root[1].end(),pair<ll,ll>{d,-INFL})).ss; ll r2=(*lower_bound(root[2].begin(),root[2].end(),pair<ll,ll>{d,-INFL})).ss; ll ans=get(r0,1,POT/2,l,r,0); ll lew=get(r0,1,POT/2,l,r,3)-1; ll prw=-get(r0,1,POT/2,l,r,4)+1; if(ans==0){ lew=r; prw=l; } if(-get(r1,1,POT/2,prw,r,1)>r)ans++; if(get(r2,1,POT/2,l,lew,2)<l)ans++; return max(ans,1LL); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...