Submission #1216494

#TimeUsernameProblemLanguageResultExecution timeMemory
1216494Adeeb_obedoMeetings (IOI18_meetings)C++20
41 / 100
1264 ms136948 KiB
#include<bits/stdc++.h> #define int long long #define ld double #define _1 first #define _2 second #define yes cout<<"Yes\n" #define nah cout<<"No\n" #define FFF ios_base::sync_with_stdio(0);cin.tie(0); #define ipr pair<int,int> #define ret return #define intt int32_t #define mid ((l+r)/2) #define pb push_back #define lll __int128 #include "meetings.h" using namespace std; int tst, ts; map<ipr,ipr>mp; intt mo = 998244353, dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0}; int mul( int x, int y ) { ret ( ( x % mo ) * ( y % mo ) ) % mo; ret x*y; } int pwo( int x, int y ) { int res = 1; for( int i = 63; i + 1; i-- ) res = mul( res, res * ( ( 1ll << i )&y ? x : 1 ) ); ret res; } int dvii( int x, int y ) { ret mul( x, pwo( y, mo - 2 ) ); } int oo( char x ) { ret ( int )x - '0'; } int lgg( int x, int y ) { int u = 0; while( x ) { u++; x /= y; } ret u; } int mun( int x, int y ) { while( x < y )x += mo; ret ( x - y ) % mo; } int add( int x, int y ) { ret x + y - ( mo * ( x + y >= mo ) ); ret x + y; } int lcm( int x, int y ) { ret ( x * y ) / __gcd( x, y ); } #define endl '\n'; const int M =1007, N = 2e5+ 7, N2 = 5e3 + 7, inf = 2e18+7 ; intt n,a[N],x,s,e,mxx; vector<intt>v[22],mv[22]; vector<ipr>vv[22]; ipr b[N][22],tr[N*4][22]; ipr cm(ipr u,ipr p,intt o){ if(p._2<u._2) swap(u,p); if(u._1+(p._2-u._2)*o>p._1) swap(u,p); ret u; } ipr bll(intt l,intt r){ if(l==0&&r==n-1){ for(intt i=0;i<n;i++) mv[a[i]].pb(i); // cout<<" dfsd"<<endl; } intt mx=-1e9,mn=1e9; for(intt i=l;i<=r;i++) mx=max(mx,a[i]),mn=min(mn,a[i]); if(mx==mn) ret {(r-l+1)*mx,r-l+1}; intt o; ipr u={inf,1}; for(intt i=l;i<=r;i++){ if(a[i]==mx) continue; if((i==l||a[i-1]==mx)&&a[i]<mx) o=i; if(a[i]<mx&&(a[i+1]==mx||i==r)){ v[mx].pb(o); vv[mx].pb({o,i}); ipr p=bll(o,i); b[v[mx].size()-1][mx]=p; u=cm(u,p,mx); } } u._1+=(r-l+1-u._2)*mx; u._2=r-l+1; ret u; } void bul(intt no,intt l,intt r){ if(l==r){ tr[no][mxx]=b[l][mxx]; ret; } bul(no*2,l,mid); bul(no*2+1,mid+1,r); ipr u=tr[no*2+1][mxx],p=tr[no*2][mxx]; tr[no][mxx]=cm(u,p,mxx); } ipr qr(intt no,intt l,intt r){ if(l>e||s>r) ret {inf,1}; if(s<=l&&r<=e) ret tr[no][mxx]; ipr u=qr(no*2+1,mid+1,r),p=qr(no*2,l,mid); ret cm(u,p,mxx); } ipr qrr(intt l,intt r,intt mx){ //cout<<l<<" "<<r<<" "<<mx<<" "; if(mp.count({l,r})) ret mp[{l,r}]; if(mx==1||l==r) ret {a[l]*(r-l+1),r-l+1}; intt o=lower_bound(mv[mx].begin(),mv[mx].end(),l)-mv[mx].begin(); //cout<<o<<" "<<mv[mx][o]<<endl; if(mv[mx][o]>r){ mp[{l,r}]=qrr(l,r,mx-1); ret mp[{l,r}]; } intt u=upper_bound(mv[mx].begin(),mv[mx].end(),r)-mv[mx].begin()-1; ipr an={inf,1}; if(mv[mx][o]>l) an=cm(an,qrr(l,mv[mx][o]-1,mx-1),mx); if(mv[mx][u]<r) an=cm(an,qrr(mv[mx][u]+1,r,mx-1),mx); //cout<<mv[mx][o]<<" "<<mv[mx][u]<<" "; intt oo=lower_bound(v[mx].begin(),v[mx].end(),mv[mx][o])-v[mx].begin(); if(vv[mx][oo]._2>r){ if(an._1==inf){ mp[{l,r}]=qrr(l,r,mx-1); ret mp[{l,r}]; } an._1+=(r-l+1-an._2)*mx; an._2=r-l+1; mp[{l,r}]=an; ret an; } intt uu=upper_bound(v[mx].begin(),v[mx].end(),mv[mx][u])-v[mx].begin()-1; s=oo,e=uu,mxx=mx; if(v[mx].size()>1) an=cm(an,qr(1,0,v[mx].size()-2),mx); an._1+=(r-l+1-an._2)*mx; an._2=r-l+1; mp[{l,r}]=an; ret an; } vector<int>minimum_costs(vector<intt> H, vector<intt> L,vector<intt> R){ n=H.size(); for(intt i=0;i<n;i++) a[i]=H[i]; bll(0,n-1); for(intt i=2;i<=20;i++){ mxx=i; if(v[i].size()) bul(1,0,v[i].size()-1); v[i].pb(n); mv[i].pb(n); vv[i].pb({n,n}); } vector<int>an; for(intt i=0;i<L.size();i++) an.pb(qrr(L[i],R[i],20)._1); ret an; }
#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...