| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 31151 | skykhs3 | Jousting tournament (IOI12_tournament) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
int K[MAXN],S[MAXN],E[MAXN],N,C,R,nn,sum[MAXN],v,mx=-1;
int seg[MAXN*4],mxseg[MAXN*4];
int query1(int lef,int rig,int lev,int x){
if(x==0) return -1;
if(lef==rig) return lef;
else{
int mid=lef+rig>>1;
if(seg[lev*2]>=x) return query1(lef,mid,lev*2,x);
else return query1(mid+1,rig,lev*2+1,x-seg[lev*2]);
}
}
void query2(int lef,int rig,int lev,int s,int e){
if(rig<s || e<lef) return;
if(s<=lef && rig<=e) seg[lev]=0;
else{
int mid=(lef+rig)/2;
query2(lef,mid,lev*2,s,e);
query2(mid+1,rig,lev*2+1,s,e);
seg[lev]=seg[lev*2]+seg[lev*2+1];
}
}
int query3(int lef,int rig,int lev,int s,int e){
if(rig<s || e<lef) return -1;
if(s<=lef && rig<=e) return mxseg[lev];
else{
int mid=lef+rig>>1;
return max(query3(lef,mid,lev*2,s,e),query3(mid+1,rig,lev*2+1,s,e));
}
}
int main()
{
scanf("%d%d%d",&N,&C,&R);
for(int i=0;i<N-1;i++) scanf("%d",&K[i]);
for(int i=0;i<C;i++) scanf("%d%d",&S[i],&E[i]);
for(nn=1;nn<N;nn*=2);
for(int i=0;i<N;i++) seg[i+nn]=1,mxseg[i+nn]=K[i];
for(int i=nn-1;i>=1;i--) seg[i]=seg[i*2]+seg[i*2+1],mxseg[i]=max(mxseg[i*2],mxseg[i*2+1]);
for(int i=0;i<C;i++){
int p2=query1(0,nn-1,1,E[i]+1),p1=query1(0,nn-1,1,S[i])+1;
query2(0,nn-1,1,p1,p2-1);
if(query3(0,nn-1,1,p1,p2-1)<=R) sum[p1]++,sum[p2+1]--;
}
int st=0;
for(int i=0;i<N;i++){
st+=sum[i];
if(mx<st){
mx=st;
v=i;
}
}
printf("%d",v);
}