Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC target("avx2")
- #pragma GCC optimization("O3")
- #pragma GCC optimization("unroll-loops")
- #include<bits/stdc++.h>
- //#include "tournament.h"
- #define rc(x) return cout<<x<<endl,0
- #define pb push_back
- #define mkp make_pair
- #define in insert
- #define er erase
- #define fd find
- #define fr first
- #define sc second
- typedef long long ll;
- typedef long double ld;
- const ll INF=0x3f3f3f3f3f3f3f3f;
- const ll llinf=(1LL<<62);
- const int inf=(1<<30);
- const int nmax=1e5+50;
- const int mod=1e9+7;
- using namespace std;
- int n,i,s[nmax],e[nmax],st[4*nmax],rs[nmax],mn[nmax],j,t,x,y,r,c,a[nmax],mx,id,l,fw[nmax],p[nmax];
- int smn[4*nmax],smx[4*nmax],lzy[4*nmax],eq[4*nmax];
- vector<pair<int,int> >lb[nmax],rb[nmax];
- vector<int>vc[nmax];
- void upd(int x,int l,int r,int p,int v)
- {
- if(l==r)
- {
- st[x]=min(st[x],v);
- return;
- }
- int mid=(l+r)/2;
- if(mid>=p)upd(2*x,l,mid,p,v);
- else upd(2*x+1,mid+1,r,p,v);
- st[x]=min(st[2*x],st[2*x+1]);
- }
- int qry(int x,int l,int r,int tl,int tr)
- {
- if(l>tr || r<tl)return inf;
- if(tl<=l && r<=tr)return st[x];
- int mid=(l+r)/2;
- return min(qry(2*x,l,mid,tl,tr),qry(2*x+1,mid+1,r,tl,tr));
- }
- void upd(int i,int v)
- {
- for(;i<=n;i+=i&(-i))fw[i]+=v;
- }
- int qry(int i)
- {
- int ans=0;
- for(;i>=1;i-=i&(-i))ans+=fw[i];
- return ans;
- }
- void build(int x,int l,int r)
- {
- eq[x]=inf;
- if(l==r)
- {
- smn[x]=smx[x]=l;
- return;
- }
- int mid=(l+r)/2;
- build(2*x,l,mid);
- build(2*x+1,mid+1,r);
- smn[x]=min(smn[2*x],smn[2*x+1]);
- smx[x]=max(smx[2*x],smx[2*x+1]);
- }
- void push(int nod,int l,int r)
- {
- if(eq[nod]!=inf)
- {
- smx[nod]=smn[nod]=eq[nod];
- if(l!=r)
- {
- eq[2*nod]=min(eq[2*nod],eq[nod]);
- eq[2*nod+1]=min(eq[2*nod+1],eq[nod]);
- }
- eq[nod]=inf;
- lzy[nod]=0;
- }
- if(!lzy[nod])return;
- smx[nod]-=lzy[nod];
- smn[nod]-=lzy[nod];
- if(l!=r)
- {
- lzy[nod*2]+=lzy[nod];
- lzy[nod*2+1]+=lzy[nod];
- }
- lzy[nod]=0;
- }
- void up(int nod,int l,int r,int tl,int tr,int v,int t)
- {
- push(nod,l,r);
- if(tl<=l && r<=tr)
- {
- if(!t)eq[nod]=v;
- else lzy[nod]+=v;
- push(nod,l,r);
- return;
- }
- int mid=(l+r)/2;
- if(tl<=mid)up(nod*2,l,mid,tl,tr,v,t);
- if(mid<tr)up(nod*2+1,mid+1,r,tl,tr,v,t);
- push(nod*2,l,mid);
- push(nod*2+1,mid+1,r);
- smx[nod]=max(smx[2*nod],smx[2*nod+1]);
- smn[nod]=min(smn[2*nod],smn[2*nod+1]);
- }
- int kth(int nod,int l,int r,int k)
- {
- if(l>r || !k)return 0;
- push(nod,l,r);
- if(l==r)return l;
- int mid=(l+r)/2;
- push(2*nod,l,mid);
- push(2*nod+1,mid+1,r);
- if(smx[2*nod]>k || (smx[2*nod]==k && smn[2*nod+1]>k))return kth(2*nod,l,mid,k);
- else return kth(2*nod+1,mid+1,r,k);
- }
- int GetBestPosition(int N,int C,int R,int K[],int S[],int E[])
- {
- n=N,c=C,r=R+1;
- for(i=1;i<n;i++)a[i]=K[i-1]+1;
- for(i=1;i<=c;i++)
- {
- s[i]=S[i-1]+1;
- e[i]=E[i-1]+1;
- }
- build(1,1,n);
- for(i=1;i<=n;i++)p[i]=i;
- for(i=1;i<=c;i++)
- {
- push(1,1,n);
- if(smn[1]==s[i])x=1;
- else x=kth(1,1,n,s[i]-1)+1;
- if(smx[1]==e[i])y=n;
- else y=kth(1,1,n,e[i]);
- if(x>=1 && x<=n && y>=1 && y<=n && x<y)up(1,1,n,x,y,s[i],0);
- if(x>=1 && x<=n && y>=1 && y<n && x<y)up(1,1,n,y+1,n,e[i]-s[i],1);
- lb[x].pb(mkp(y,i));
- rb[y].pb(mkp(x,i));
- s[i]=x,e[i]=y;
- }
- for(i=1;i<=4*n;i++)st[i]=c;
- j=1,l=0;
- for(i=1;i<=n;i++)
- {
- for(;j<=l;j++)
- {
- for(t=0;t<lb[j].size();t++)
- {
- upd(1,1,n,lb[j][t].fr,lb[j][t].sc);
- }
- }
- mn[i]=qry(1,1,n,i,n);
- if(a[i]>r)l=i;
- }
- for(i=1;i<=4*n;i++)st[i]=c;
- j=n,l=n+1;
- for(i=n;i>=1;i--)
- {
- if(a[i]>r)l=i;
- for(;j>l;j--)
- {
- for(t=0;t<rb[j].size();t++)
- {
- upd(1,1,n,rb[j][t].fr,rb[j][t].sc);
- }
- }
- mn[i]=min(mn[i],qry(1,1,n,1,i));
- vc[mn[i]].pb(i);
- }
- for(i=1;i<=c;i++)
- {
- for(j=0;j<vc[i].size();j++)
- {
- rs[vc[i][j]]=qry(vc[i][j]);
- }
- upd(s[i],1);
- upd(e[i]+1,-1);
- }
- mx=-1;
- for(i=1;i<=n;i++)
- {
- if(mx<rs[i])
- {
- mx=rs[i];
- id=i;
- }
- }
- return id-1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement