#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 qr(int x,int l,int r,int tl,int tr)
{
if(tl>r || tr<l)return inf;
push(x,l,r);
if(tl<=l && r<=tr)return smn[x];
int mid=(l+r)/2;
return min(qr(2*x,l,mid,tl,tr),qr(2*x+1,mid+1,r,tl,tr));
}
/*int main()
{
freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n>>c>>r;
r++;
for(i=1;i<n;i++)
{
cin>>a[i];
a[i]++;
}
for(i=1;i<=c;i++)
{
cin>>s[i]>>e[i];
s[i]++,e[i]++;
}
build(1,1,n);
for(i=1;i<=n;i++)p[i]=i;
for(i=1;i<=c;i++)
{
//for(j=1;j<=n;j++)cout<<qr(1,1,n,j,j)<<" ";
//cout<<endl;
/*for(j=1;j<=n;j++)
{
if(p[j]==s[i])
{
x=j;
break;
}
}
for(j=n;j>=1;j--)
{
if(p[j]==e[i])
{
y=j;
break;
}
}
for(j=y+1;j<=n;j++)p[j]-=(e[i]-s[i]);
for(j=x;j<=y;j++)p[j]=s[i];*/
/*x=kth(1,1,n,s[i]-1)+1,y=kth(1,1,n,e[i]);
up(1,1,n,x,y,s[i],0);
if(y<n)up(1,1,n,y+1,n,e[i]-s[i],1);
//if(i<=3)cout<<qr(1,1,n,3,3)<<" "<<qr(1,1,n,4,4)<<" "<<qr(1,1,n,471,471)<<" "<<qr(1,1,n,472,472)<<" "<<qr(1,1,n,473,473)<<" "<<qr(1,1,n,491,491)<<" "<<qr(1,1,n,492,492)<<endl;
lb[x].pb(mkp(y,i));
rb[y].pb(mkp(x,i));
s[i]=x,e[i]=y;
cout<<x<<" "<<y<<endl;
}
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;
}
}
cout<<mx<<" "<<id<<endl;
return 0;
}
/*
5 3 3
1 0 2 4
1 3
0 1
0 1
*/
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++)
{
//for(j=1;j<=n;j++)cout<<qr(1,1,n,j,j)<<" ";
//cout<<endl;
/*for(j=1;j<=n;j++)
{
if(p[j]==s[i])
{
x=j;
break;
}
}
for(j=n;j>=1;j--)
{
if(p[j]==e[i])
{
y=j;
break;
}
}
for(j=y+1;j<=n;j++)p[j]-=(e[i]-s[i]);
for(j=x;j<=y;j++)p[j]=s[i];*/
x=kth(1,1,n,s[i]-1)+1,y=kth(1,1,n,e[i]);
up(1,1,n,x,y,s[i],0);
if(y<n)up(1,1,n,y+1,n,e[i]-s[i],1);
//if(i<=3)cout<<qr(1,1,n,3,3)<<" "<<qr(1,1,n,4,4)<<" "<<qr(1,1,n,471,471)<<" "<<qr(1,1,n,472,472)<<" "<<qr(1,1,n,473,473)<<" "<<qr(1,1,n,491,491)<<" "<<qr(1,1,n,492,492)<<endl;
lb[x].pb(mkp(y,i));
rb[y].pb(mkp(x,i));
s[i]=x,e[i]=y;
//if(i<=10)cout<<x<<" "<<y<<endl;
}
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;
}
Compilation message
tournament.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("O3")
tournament.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization("unroll-loops")
tournament.cpp:153:3: warning: "/*" within comment [-Wcomment]
/*for(j=1;j<=n;j++)
tournament.cpp:230:1: warning: "/*" within comment [-Wcomment]
/*
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:285:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(t=0;t<lb[j].size();t++)
~^~~~~~~~~~~~~
tournament.cpp:300:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(t=0;t<rb[j].size();t++)
~^~~~~~~~~~~~~
tournament.cpp:310:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<vc[i].size();j++)
~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
7416 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
7416 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
7544 KB |
Output is correct |
| 2 |
Correct |
20 ms |
8440 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
7928 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
92 ms |
13748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
