제출 #576511

#제출 시각아이디문제언어결과실행 시간메모리
576511benson1029마상시합 토너먼트 (IOI12_tournament)C++14
0 / 100
37 ms3424 KiB
#include<bits/stdc++.h> using namespace std; int seg[400005]; int v[400005]; int tmp[400005]; int l[100005], r[100005]; int seg2[400005]; int k[100005]; void seg_set(int x, int l, int r, int p, int v) { if(l==r) { seg[x] = v; } else { if(p<=(l+r)/2) seg_set(x*2, l, (l+r)/2, p, v); else seg_set(x*2+1, (l+r)/2+1, r, p, v); seg[x] = seg[x*2] + seg[x*2+1]; } } int seg_qry(int x, int l, int r, int v) { if(l==r) return l; else { if(v <= seg[x*2]) return seg_qry(x*2, l, (l+r)/2, v); else return seg_qry(x*2+1, (l+r)/2+1, r, v-seg[x*2]); } } void seg2_build(int x, int l, int r) { if(l==r) seg2[x] = k[l]; else { seg2_build(x*2, l, (l+r)/2); seg2_build(x*2+1, (l+r)/2+1, r); seg2[x] = max(seg2[x*2], seg2[x*2+1]); } } int seg2_qry(int x, int l, int r, int ll, int rr) { if(l > rr || r < ll) return -1e9; if(ll <= l && r <= rr) return seg2[x]; return max(seg2_qry(x*2, l, (l+r)/2, ll, rr), seg2_qry(x*2+1, (l+r)/2+1, r, ll, rr)); } int diff[100005]; int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) { for(int i=0; i<N; i++) seg_set(1, 0, N-1, i, 1); for(int i=0; i<C; i++) { S[i]++; E[i]++; for(int j=S[i]; j<=E[i]; j++) { tmp[j] = seg_qry(1, 0, N-1, j); } l[i] = tmp[S[i]]; r[i] = tmp[E[i]] + v[tmp[E[i]]]; for(int j=S[i]+1; j<=E[i]; j++) { seg_set(1, 0, N-1, tmp[j], 0); } v[tmp[S[i]]] += (E[i] - S[i]); } for(int i=0; i<N-1; i++) k[i] = K[i]; seg2_build(1, 0, N-2); for(int i=0; i<C; i++) { if(R > seg2_qry(1, 0, N-2, l[i], r[i]-1)) { diff[l[i]]++; diff[r[i]+1]--; } } int ans = -1, pos = -1; for(int i=0; i<N; i++) { if(i) diff[i] += diff[i-1]; if(diff[i] > ans) { ans = diff[i]; pos = i; } } return pos; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...