oj.uz

Submission #137412

# Submission time Handle Problem Language Result Execution time Memory
137412 2019-07-27T17:02:33 Z jangwonyoung Jousting tournament (IOI12_tournament) C++14
100 / 100
 165 ms 10280 KB 
#include<bits/stdc++.h>
using namespace std;
const int ts=262144;
const int N=1e5+1,Q=1e5+1;
int n,q,k;
int mn[ts];
int a[N];
int lq[Q],rq[Q];
int mj[N];
void build(int id,int l,int r){
	if(l==r) mn[id]=a[l];
	else{
		int mid=(l+r)/2;
		build(id*2,l,mid);build(id*2+1,mid+1,r);
		mn[id]=min(mn[id*2],mn[id*2+1]);
	}
}
int qry(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return 1e9;
	if(ql<=l && r<=qr) return mn[id];
	int mid=(l+r)/2;
	return min(qry(id*2,l,mid,ql,qr),qry(id*2+1,mid+1,r,ql,qr));
}
int cnt[ts];
bool die[ts];
void push2(int id){
	if(!die[id]) return;
	die[id*2]=true;cnt[id*2]=0;
	die[id*2+1]=true;cnt[id*2+1]=0;
	die[id]=false;
}
void build2(int id,int l,int r){
	if(l==r) cnt[id]=1;
	else{
		int mid=(l+r)/2;
		build2(id*2,l,mid);build2(id*2+1,mid+1,r);
		cnt[id]=cnt[id*2]+cnt[id*2+1];
	}
}
void upd2(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		die[id]=true;cnt[id]=0;
		return;
	}
	push2(id);
	int mid=(l+r)/2;
	upd2(id*2,l,mid,ql,qr);
	upd2(id*2+1,mid+1,r,ql,qr);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
}
int qry2(int id,int l,int r,int x){
	if(l==r) return l;
	push2(id);
	int mid=(l+r)/2;
	if(cnt[id*2]>=x) return qry2(id*2,l,mid,x);
	return qry2(id*2+1,mid+1,r,x-cnt[id*2]);
}
int mx[ts],wn[ts];
int mp[ts];
bool dead[ts];
void push3(int id){
	if(!dead[id*2]) wn[id*2]+=wn[id],mx[id*2]+=wn[id];
	if(!dead[id*2+1]) wn[id*2+1]+=wn[id],mx[id*2+1]+=wn[id];
	if(dead[id]){
		dead[id*2]=dead[id*2+1]=true;
	}
	wn[id]=0;
}
void build3(int id,int l,int r){
	if(l==r) mp[id]=l;
	else{
		int mid=(l+r)/2;
		build3(id*2,l,mid);build3(id*2+1,mid+1,r);
		mp[id]=l;
	}
}
void upd3a(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		if(!dead[id]) wn[id]++,mx[id]++;
		return;
	}
	push3(id);
	int mid=(l+r)/2;
	upd3a(id*2,l,mid,ql,qr);
	upd3a(id*2+1,mid+1,r,ql,qr);
	if(mx[id*2]>=mx[id*2+1]) mx[id]=mx[id*2],mp[id]=mp[id*2];
	else mx[id]=mx[id*2+1],mp[id]=mp[id*2+1];
}
void upd3b(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		dead[id]=true;
		return;
	}
	push3(id);
	int mid=(l+r)/2;
	upd3b(id*2,l,mid,ql,qr);
	upd3b(id*2+1,mid+1,r,ql,qr);
	if(mx[id*2]>=mx[id*2+1]) mx[id]=mx[id*2],mp[id]=mp[id*2];
	else mx[id]=mx[id*2+1],mp[id]=mp[id*2+1];
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	int n=N,q=C,k=n-R;
	for(int i=1; i<n ;i++) a[i]=n-K[i-1],mj[i]=i;
	for(int i=1; i<=q ;i++) lq[i]=S[i-1]+1,rq[i]=E[i-1]+1;
	build(1,1,n);
	build2(1,1,n);
	build3(1,1,n);
	for(int i=1; i<=q ;i++){
		lq[i]=qry2(1,1,n,lq[i]);
		rq[i]=mj[qry2(1,1,n,rq[i])];
		mj[lq[i]]=rq[i];
		upd2(1,1,n,lq[i]+1,rq[i]);
		int mini=qry(1,1,n,lq[i],rq[i]-1);
		if(mini<k) upd3b(1,1,n,lq[i],rq[i]);
		else upd3a(1,1,n,lq[i],rq[i]);
	}
	return mp[1]-1;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 8 ms 888 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 8 ms 888 KB Output is correct
5 Correct 7 ms 888 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 8 ms 888 KB Output is correct
8 Correct 8 ms 888 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 9 ms 1016 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4952 KB Output is correct
2 Correct 161 ms 10280 KB Output is correct
3 Correct 30 ms 5752 KB Output is correct
4 Correct 154 ms 10232 KB Output is correct
5 Correct 152 ms 10104 KB Output is correct
6 Correct 134 ms 9208 KB Output is correct
7 Correct 156 ms 10232 KB Output is correct
8 Correct 165 ms 10232 KB Output is correct
9 Correct 22 ms 5468 KB Output is correct
10 Correct 33 ms 7928 KB Output is correct