| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 393577 | Hazem | Jousting tournament (IOI12_tournament) | C++14 | 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>
//#include "grader.h"
using namespace std;
#define S second
#define F first
#define LL long long
const int N1 = 4e5+10;
const LL MOD = 1e9+7;
const LL LINF = 1e18;
const LL INF = 1e9;
int sizes[N1],par[N1],sum[N1],lasttaken[N1],mx[N1];
int tree[N1],val[N1],nxt[N];
void update(int v,int l,int r,int pos,int val){
if(l==r){
tree[v] = val;
return ;
}
int mid = (l+r)/2;
if(pos<=mid)
update(v*2,l,mid,pos,val);
else
update(v*2+1,mid+1,r,pos,val);
tree[v] = max(tree[v*2],tree[v*2+1]);
}
/*
int get(int v,int tl,int tr,int l,int r,int pos){
if(tl>=l&&tr<=r)
return tree[v];
if(tl>r||tr<l)
return -INF;
}
*/
pair<int,int> find_set(int a){
if(a==par[a])
return make_pair(a,sum[a]);
else {
pair<int,int>p = find_set(par[a]);
sum[a] += p.S-lasttaken[a];
par[a] = p.F;
lasttaken[a] = sum[p.F];
return make_pair(p.F,sum[a]);
}
}
void merge_set(int u,int v){
u = find_set(u).F;
v = find_set(v).F;
if(u==v)return ;
if(sizes[u]<sizes[v])swap(u,v);
sizes[u] += sizes[v];
par[v] = u;
mx[u] = max(mx[u],mx[v]);
nxt[u] = max(nxt[u],nxt[v]);
}
void add(int u){
u = find_set(u).F;
sum[u]++;
lasttaken[u]++;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int n = N;
for(int i=1;i<n;i++)
val[i] = K[i-1];
val[n] = R;
int cur = n;
int curans = 0,curret = n-1;
while(cur--){
for(int i = 1;i<=n;i++)
sizes[i] = 1,par[i] = i,mx[i] = val[i];
int ret = 0;
for(int i=0;i<C;i++){
int l = S[i]+1,r = E[i]+1;
vector<int>vec;
int cnt = 0;
for(int j=1;j<=n;j++){
if(find_set(j).F!=find_set(j-1).F){
cnt++;
if(cnt>=l&&cnt<=r)
vec.push_back(j);
}
j = nxt[find_set(j).F]-1;
}
for(int j=0;j<vec.size()-1;j++)
merge_set(vec[j],vec[j+1]);
int u = find_set(vec[0]).F;
//printf("%d ",mx[u]);
if(mx[u]==R)ret++;
}
if(ret>=curans)curret = cur,curans = ret;
swap(val[cur],val[cur+1]);
}
return curret;
}