oj.uz

Submission #577198

# Submission time Handle Problem Language Result Execution time Memory
577198 2022-06-14T09:14:01 Z WongChun1234 Jousting tournament (IOI12_tournament) C++14
100 / 100
 624 ms 25928 KB 
//#include"grader.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int N=100050;
int n,c,r,a[N<<1],s[N<<1],e[N],lift[25][N<<1],mxup[N<<1],cnt[N<<2],par[N<<1],seg[N<<2],cb=0,cbx=1;
bool clr[N<<2];
set<pair<int,int>> currrange;
vector<pair<int,int>> ndel;
void build(int id,int l,int r){
	if (l==r){
		cnt[id]=1;
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid); build(id*2+1,mid+1,r);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
}
void pushdown(int id){
	cnt[id]=0; clr[id]=1;
}
int query(int id,int l,int r,int q){
	if (l==r) return l;
	int mid=(l+r)/2;
	if (clr[id]) pushdown(id*2),pushdown(id*2+1);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
	clr[id]=0;
	if (cnt[id*2]>=q) return query(id*2,l,mid,q);
	else return query(id*2+1,mid+1,r,q-cnt[id*2]);
}
void fix(int id,int l,int r,int ql,int qr){
	if (ql>r||qr<l) return;
	if (ql<=l&&qr>=r){
		pushdown(id);
		return;
	}
	int mid=(l+r)/2;
	fix(id*2,l,mid,ql,qr); fix(id*2+1,mid+1,r,ql,qr);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
}
void add(int id,int l,int r,int q){
	if (q>r||q<l) return;
	if (l==r){
		cnt[id]=1;
		return;
	}
	if (clr[id]) pushdown(id*2),pushdown(id*2+1);
	clr[id]=0;
	int mid=(l+r)/2;
	add(id*2,l,mid,q); add(id*2+1,mid+1,r,q);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
}
void bmin(int id,int l,int r){
	if (l==r){
		seg[id]=a[l-1];
		return;
	}
	int mid=(l+r)/2;
	bmin(id*2,l,mid); bmin(id*2+1,mid+1,r);
	seg[id]=max(seg[id*2],seg[id*2+1]);
}
int qmx(int id,int l,int r,int ql,int qr){
	if (ql>r||qr<l) return INT_MIN;
	if (ql<=l&&qr>=r) return seg[id];
	int mid=(l+r)/2;
	return max(qmx(id*2,l,mid,ql,qr),qmx(id*2+1,mid+1,r,ql,qr));
}
int GetBestPosition(int _N, int C, int R, int *K, int *S, int *E) {
	n=_N; c=C;
	for (int i=0;i<n-1;i++) a[i]=K[i];
	build(1,1,n+1);
	for (int i=1;i<=n;i++) currrange.insert({i,i});
	for (int i=0;i<c;i++){
		int ll=query(1,1,n+1,S[i]+1),rr=query(1,1,n+1,E[i]+2)-1;
		fix(1,1,n+1,ll,rr);
		add(1,1,n+1,ll);
		s[n+i+1]=ll; e[n+i+1]=rr;
		ndel.clear();
		for (auto ff=currrange.upper_bound({ll,-1});ff!=currrange.upper_bound({rr+1,-1});ff++){
			ndel.push_back(*ff);
			par[(*ff).second]=n+i+1;
		}
		for (auto j:ndel) currrange.erase(j);
		currrange.insert({ll,n+i+1});
	}
	for (int j=0;j<=16;j++) lift[j][n+c]=n+c;
	for (int i=n+c-1;i>=1;i--){
		mxup[i]=mxup[par[i]]+1;
		lift[0][i]=par[i];
		for (int j=1;j<=16;j++) lift[j][i]=lift[j-1][lift[j-1][i]];
	}
	bmin(1,1,n-1);
	for (int i=1;i<=n;i++){
		int curr=i,val=0;
		for (int j=16;j>=0;j--){
			//if (j==20) cerr<<curr<<":"<<s[lift[j][curr]]<<"-"<<e[lift[j][curr]]<<" "<<qmx(1,1,n-1,s[lift[j][curr]],i-1)<<","<<qmx(1,1,n-1,i,e[lift[j][curr]]-1)<<"\n";
			if (R>max(qmx(1,1,n-1,s[lift[j][curr]],i-1),qmx(1,1,n-1,i,e[lift[j][curr]]-1))) curr=lift[j][curr],val+=(1<<j);
		}
		if (val>cb) cb=val,cbx=i;
	}
	return cbx-1;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 21 ms 1664 KB Output is correct
3 Correct 13 ms 1364 KB Output is correct
4 Correct 22 ms 1596 KB Output is correct
5 Correct 19 ms 1632 KB Output is correct
6 Correct 17 ms 1492 KB Output is correct
7 Correct 21 ms 1716 KB Output is correct
8 Correct 27 ms 1728 KB Output is correct
9 Correct 11 ms 1236 KB Output is correct
10 Correct 19 ms 1636 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 10756 KB Output is correct
2 Correct 621 ms 25928 KB Output is correct
3 Correct 405 ms 17256 KB Output is correct
4 Correct 561 ms 25916 KB Output is correct
5 Correct 624 ms 25168 KB Output is correct
6 Correct 431 ms 22452 KB Output is correct
7 Correct 582 ms 25924 KB Output is correct
8 Correct 603 ms 25928 KB Output is correct
9 Correct 339 ms 16808 KB Output is correct
10 Correct 369 ms 16800 KB Output is correct