제출 #708972

#제출 시각아이디문제언어결과실행 시간메모리
708972ToroTN마상시합 토너먼트 (IOI12_tournament)C++14
0 / 100
141 ms3508 KiB
#include<bits/stdc++.h> using namespace std; //#include "grader.cpp" int n,c,r,a[100005],x[100005],y[100005],seg[400005],lz[400005],seg2[400005]; int l,late,sweep[100005]; void build2(int tree,int st,int ed) { int md=(st+ed)/2; if(st==ed) { seg2[tree]=a[st]; return; } build2(2*tree,st,md); build2(2*tree+1,md+1,ed); seg2[tree]=max(seg2[2*tree],seg2[2*tree+1]); } int query2(int tree,int st,int ed,int l,int r) { int md=(st+ed)/2; if(st>r||ed<l)return -1e9; if(st>=l&&ed<=r)return seg2[tree]; return max(query2(2*tree,st,md,l,r),query2(2*tree+1,md+1,ed,l,r)); } void build(int tree,int st,int ed) { int md=(st+ed)/2; if(st==ed) { seg[tree]=1; return; } build(2*tree,st,md); build(2*tree+1,md+1,ed); seg[tree]=seg[2*tree]+seg[2*tree+1]; } void update(int tree,int st,int ed,int l,int r) { int md=(st+ed)/2; if(st>=l&&ed<=r)lz[tree]=1; if(st!=ed) { if(lz[tree]==1) { lz[2*tree]=1; lz[2*tree+1]=1; } } if(lz[tree]==1)seg[tree]=0; lz[tree]=0; if(st>r||ed<l)return; if(st>=l&&ed<=r)return; update(2*tree,st,md,l,r); update(2*tree+1,md+1,ed,l,r); seg[tree]=seg[2*tree]+seg[2*tree+1]; } int query(int tree,int st,int ed,int l,int r) { int md=(st+ed)/2; if(st!=ed) { if(lz[tree]==1) { lz[2*tree]=1; lz[2*tree+1]=1; } } if(lz[tree]==1)seg[tree]=0; lz[tree]=0; if(st>r||ed<l)return 0; if(st>=l&&ed<=r)return seg[tree]; return query(2*tree,st,md,l,r)+query(2*tree+1,md+1,ed,l,r); } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { n=N,c=C,late=R+1; for(int i=0;i<N-1;i++) { a[i+1]=K[i]+1; } for(int i=0;i<c;i++) { x[i+1]=S[i]+1,y[i+1]=E[i]+1; } build2(1,1,n-1); /*for(int i=1;i<n;i++)printf("%d ",a[i]); printf("\n"); for(int i=1;i<=c;i++)printf("%d %d\n",x[i],y[i]);*/ /*for(int i=1;i<n;i++) { for(int j=i;j<n;j++) { printf("%d %d %d\n",i,j,query2(1,1,n-1,i,j)); } }*/ build(1,1,n); for(int i=1;i<=c;i++) { int st=1,md,ed=n; //printf("x=%d y=%d\n",x[i],y[i]); while(ed>=st) { md=(st+ed)/2; if(query(1,1,n,1,md)<x[i]) { st=md+1; }else { ed=md-1; } } l=st; //printf("%d %d %d\n",st,md,ed); st=1,ed=n; while(ed>=st) { md=(st+ed)/2; if(query(1,1,n,1,md)<y[i]) { st=md+1; }else { ed=md-1; } } //printf("%d %d %d\n",st,md,ed); r=st; if(late>query2(1,1,n-1,l,r-1)) { sweep[l]+=1; sweep[r+1]-=1; } if(l<r) { //printf("chk%d\n",i); update(1,1,n,l,r-1); } // for(int j=1;j<=n;j++) // { // for(int k=j;k<=n;k++) // { // printf("%d %d %d\n",j,k,query(1,1,n,j,k)); // } // } //printf("%d %d\n",l,r); //break; } for(int i=1;i<=n;i++)sweep[i]=sweep[i-1]+sweep[i]; int mx=-1e9,ans; for(int i=1;i<=n;i++) { if(sweep[i]>mx)mx=sweep[i]; } for(int i=1;i<=n;i++) { if(sweep[i]==mx) { ans=i-1; break; } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:162:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  162 |     return ans;
      |            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...