| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 945979 | teacup | 마상시합 토너먼트 (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
typedef vector<int> vi;
#define iii tuple<int,int,int>
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef map<int,int> mii;
struct node{
int32_t s,e;
int mn,mx,sum,add_val,set_val;
bool lset;
node *l, *r;
node (int _s, int _e, int A[]=NULL): s(_s), e(_e), mn(0), mx(0), sum(0), lset(0), add_val(0), set_val(0), l(NULL), r(NULL){
if (A==NULL) return;
if (s==e) mn=mx=sum=A[s];
else{
l=new node(s, (s+e)>>1,A), r=new node((s+e+2)>>1,e,A);
combine();
}
}
void create_children(){
if (s==e) return;
if (l!=NULL) return;
int m=(s+e)>>1;
l=new node(s,m);
r=new node(m+1,e);
}
void self_set(int v){
lset=1;
mn=mx=set_val=v;
sum=v*(e-s+1);
add_val=0;
}
void self_add(int v){
if (lset) {self_set(v+set_val); return;}
mn+=v, mx+=v, add_val+=v;
sum+=v*(e-s+1);
}
void lazy(){
if (s==e) return;
if (lset){
l->self_set(set_val), r->self_set(set_val);
set_val=0; lset=0;
}
if (add_val!=0){
l->self_add(add_val), r->self_add(add_val);
add_val=0;
}
}
void combine(){
if (l==NULL) return;
sum=l->sum +r->sum;
mn=min(l->mn,r->mn);
mx=max(l->mx,r->mx);
}
#define UPDATE(name)\
void name(int x, int y, int v){\
if (s==x&&e==y) {self_##name(v); return;}\
int m=(s+e)>>1; \
create_children(); lazy();\
if (x<=m) l->name(x,min(y,m),v);\
if (y>m) r->name(max(x,m+1),y,v);\
combine();\
}
UPDATE(add)
UPDATE(set)
#define QUERY(name,fn,var,lazyfn)\
int range_##name(int x, int y){\
if (s==x&&e==y) return var;\
if (l==NULL||lset) return lazyfn(var);\
int m=(s+e)>>1; lazy();\
if (y<=m) return l->range_##name(x,y);\
if (x>m) return r->range_##name(x,y);\
return fn(l->range_##name(x,m), r->range_##name(m+1,y));\
}
#define SAME(var) (var)
#define PART(var) ((var)/(e-s+1)*(y-x+1))
#define SUM(a,b) ((a)+(b))
QUERY(min,min,mn,SAME)
QUERY(max,max,mx,SAME)
QUERY(sum,SUM,sum,PART)
~node(){
if (l!=NULL) delete l;
if (r!=NULL) delete r;
}
}*ranks, *alive, *wins;
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
ranks = new node(0,N+5);
alive = new node(0,N+5);
wins = new node(0,N+5);
for (int i=0; i<N-1; i++) ranks->set(i, i, K[i]);
alive.set(0,N,1);
for (int i=0; i<C; i++){
int l=0,r=N-1, actualS, actualE;
while (l<r){
int m = (l+r)/2;
if (alive->range_sum(0,m)<=S[i]) l=m+1;
else r=m;
}
actualS = l;
l=0; r=N-1;
while (l<r2){
int m = l+(r2-l)/2;
if (root2->range_sum(0,m)<=E[i]+1) l=m+1;
else r2=m;
}
int actualE=l;
alive->set(start,start,1);
alive->set(start+1,end,0);
if (ranks->range_max(actualS, actualE-1) < R){
wins->add(actualS,actualE,1);
}
}
int maxPos=-1, maxWins=0;
for (int i=0; i<N; i++){
int currWins = wins->range_max(i,i);
if (currWins > maxWins){
maxWins = currWins;
maxPos = i;
}
}
return ans;
}