제출 #422612

#제출 시각아이디문제언어결과실행 시간메모리
422612Bill_00마상시합 토너먼트 (IOI12_tournament)C++14
0 / 100
80 ms7852 KiB
#include <bits/stdc++.h> using namespace std; int lazy[1000000],node[1000000],mx[1000000],another[1000000],lazyanother[1000000]; void update(int id,int l,int r,int L,int R,int x){ if(lazy[id]!=-1){ node[id]=(lazy[id]*(r-l+1)); lazy[id*2]=lazy[id]; lazy[id*2+1]=lazy[id]; lazy[id]=-1; } if(r<L || R<l) return; if(L<=l && r<=R){ node[id]=(x*(r-l+1)); lazy[id*2]=x; lazy[id*2+1]=x; return; } int m=l+r>>1; update(id*2,l,m,L,R,x); update(id*2+1,m+1,r,L,R,x); node[id]=node[id*2]+node[id*2+1]; } int query(int id,int l,int r,int x){ if(lazy[id]!=-1){ node[id]=(lazy[id]*(r-l+1)); int m=l+r>>1; node[id*2]=lazy[id]*(m-l+1); node[id*2+1]=lazy[id]*(r-m); lazy[id*4]=lazy[id]; lazy[id*4+1]=lazy[id]; lazy[id*4+2]=lazy[id]; lazy[id*4+3]=lazy[id]; lazy[id]=-1; } if(l==r) return l; int m=l+r>>1; if(node[id*2]>=x) return query(id*2,l,m,x); else return query(id*2+1,m+1,r,x-node[id*2]); } int rightt[100005]; void build(int id,int l,int r,int pos,int x){ if(l==r){ mx[id]=x; return; } int m=l+r>>1; if(m>=x) build(id*2,l,m,pos,x); else build(id*2+1,m+1,r,pos,x); mx[id]=max(mx[id*2],mx[id*2+1]); } int query1(int id,int l,int r,int L,int R){ if(r<L || R<l) return 0; if(L<=l && r<=R) return mx[id]; int m=l+r>>1; return max(query1(id*2,l,m,L,R),query1(id*2+1,m+1,r,L,R)); } void update1(int id,int l,int r,int L,int R){ another[id]+=(lazyanother[id]*(r-l+1)); lazyanother[id*2]+=lazyanother[id]; lazyanother[id*2+1]+=lazyanother[id]; lazyanother[id]=0; if(r<L || R<l) return; if(L<=l && r<=R){ another[id]+=(r-l+1); lazyanother[id*2]++; lazyanother[id*2+1]++; return; } int m=l+r>>1; update1(id*2,l,m,L,R); update1(id*2+1,m+1,r,L,R); another[id]=another[id*2]+another[id*2+1]; } int query2(int id,int l,int r,int pos){ another[id]+=(lazyanother[id]*(r-l+1)); lazyanother[id*2]+=lazyanother[id]; lazyanother[id*2+1]+=lazyanother[id]; lazyanother[id]=0; if(l==r) return another[id]; int m=l+r>>1; if(m>=pos) return query2(id*2,l,m,pos); else return query2(id*2+1,m+1,r,pos); } int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { memset(lazy,-1,sizeof(lazy)); for(int i=0;i<N;i++){ update(1,0,N-1,i,i,1); rightt[i]=i; } for(int i=0;i<(N-1);i++){ build(1,0,N-1,i,K[i]); } // cout << node[1] << '\n'; for(int i=0;i<C;i++){ int x=query(1,0,N-1,S[i]+1); int y=query(1,0,N-1,E[i]+1); // cout << x << ' ' << y << '\n'; update(1,0,N-1,x+1,y,0); rightt[x]=rightt[y]; int lol=query1(1,0,N-1,x,rightt[y]-1); if(R>lol) update1(1,0,N-1,x,rightt[x]); } pair<int,int>answer={0,-1000000000}; for(int i=0;i<N;i++){ answer=max(answer,{query2(1,0,N-1,i),-i}); } return -answer.second; }

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

tournament.cpp: In function 'void update(int, int, int, int, int, int)':
tournament.cpp:18:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |  int m=l+r>>1;
      |        ~^~
tournament.cpp: In function 'int query(int, int, int, int)':
tournament.cpp:26:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int m=l+r>>1;
      |         ~^~
tournament.cpp:36:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |  int m=l+r>>1;
      |        ~^~
tournament.cpp: In function 'void build(int, int, int, int, int)':
tournament.cpp:46:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int m=l+r>>1;
      |        ~^~
tournament.cpp: In function 'int query1(int, int, int, int, int)':
tournament.cpp:54:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |  int m=l+r>>1;
      |        ~^~
tournament.cpp: In function 'void update1(int, int, int, int, int)':
tournament.cpp:69:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |  int m=l+r>>1;
      |        ~^~
tournament.cpp: In function 'int query2(int, int, int, int)':
tournament.cpp:80:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |  int m=l+r>>1;
      |        ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...