| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1017786 | NintsiChkhaidze | Jousting tournament (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#include "tournament.h"
#define pii pair <int,int>
#define f first
#define s second
#define left h*2,l,(l+r)/2
#define right h*2+1,(l+r)/2+1,r
using namespace std;
const int M = 5000+5;
int arr[M];
bool lz[4*M];
pair<pii,int> t[4*M];
void build(int h,int l,int r){
lz[h] = 0;
if (l == r){
t[h] = {{arr[l],l},1};
return;
}
build(left);
build(right);
t[h].s=t[h*2].s+t[h*2+1].s;
t[h].f=max(t[h*2].f,t[h*2+1].f);
}
void push(int h){
if(!lz[h]) return ;
lz[h*2] |= lz[h];
lz[h*2+1] |= lz[h];
t[h*2] = t[h*2+1] = {{0,0},0};
lz[h]=0;
}
void updrange(int h,int l,int r,int L,int R){
if (r < L || R < l) return;
if (L <= l && r <= R) {
t[h] = {{0,0},0};
lz[h] = 1;
return;
}
push(h);
updrange(left,L,R);
updrange(right,L,R);
t[h].s=t[h*2].s+t[h*2+1].s;
t[h].f=max(t[h*2].f,t[h*2+1].f);
}
void upd(int h,int l,int r,int idx){
if (l == r){
t[h] = {{arr[l],l},1};
return;
}
push(h);
if(idx>(l+r)/2) upd(right,idx);
else upd(left,idx);
t[h].s=t[h*2].s+t[h*2+1].s;
t[h].f=max(t[h*2].f,t[h*2+1].f);
}
int get(int h,int l,int r,int k){
if (l == r) return l;
push(h);
if (t[h*2].s >= k) return get(left,k);
return get(right,k-t[h*2].s);
}
pii getmax(int h,int l,int r,int L,int R){
if (r < L || R < l) return {0,0};
if (L <= l && r <= R) return t[h].f;
push(h);
return max(getmax(left,L,R),getmax(right,L,R));
}
int GetBestPosition(int N, int C, int R, int K[], int S[], int E[]){
int n = N;
int ans=-1,pos=-1;
for (int i=0;i<N;i++){
vector <int> v;
int l = 0;
for (int j = 0; j < N; j++){
if (i == j) v.pb(R);
else v.pb(K[l++]);
}
for (int j = 1; j <= n; j++){
arr[j] = v[j - 1] + 1;
}
build(1,1,n);
int cur = 0;
for (int j = 0; j < C; j++){
int l = S[j] + 1,r = E[j] + 1;
int l1 = get(1,1,n,l);
int r1 = get(1,1,n,r);
pii res = getmax(1,1,n,l1,r1);
if (res.f == R + 1) cur += 1;
updrange(1,1,n,l1,r1);
upd(1,1,n,res.s);
}
if (cur > ans){
ans = cur;
pos = i;
}
}
return pos;
}