Submission #518805

#	Time	Username	Problem	Language	Result	Execution time	Memory
518805		AdamGS	Jousting tournament (IOI12_tournament)	C++17	100 / 100	83 ms	6888 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
int tr[4*LIM], lazy[4*LIM], ma[4*LIM], sum[4*LIM], N=1, n, m, k;
void spl(int v) {
	tr[2*v]=0;
	tr[2*v+1]=0;
	lazy[2*v]=1;
	lazy[2*v+1]=1;
	lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b) {
	if(l>b || r<a) return;
	if(a<=l && r<=b) {
		tr[v]=0;
		lazy[v]=1;
		return;
	}
	if(lazy[v]) spl(v);
	int mid=(l+r)/2;
	upd(2*v, l, mid, a, b);
	upd(2*v+1, mid+1, r, a, b);
	tr[v]=tr[2*v]+tr[2*v+1];
}
int znajdz(int v, int k) {
	if(v>=N) return v-N;
	if(lazy[v]) spl(v);
	if(tr[2*v]>=k) return znajdz(2*v, k);
	return znajdz(2*v+1, k-tr[2*v]);
}
int cnt(int l, int r) {
	l+=N; r+=N;
	int ans=max(ma[l], ma[r]);
	while(l/2!=r/2) {
		if(l%2==0) ans=max(ans, ma[l+1]);
		if(r%2==1) ans=max(ans, ma[r-1]);
		l/=2; r/=2;
	}
	return ans;
}
void dodaj(int l, int r) {
	l+=N; r+=N;
	++sum[l];
	if(l!=r) ++sum[r];
	while(l/2!=r/2) {
		if(l%2==0) ++sum[l+1];
		if(r%2==1) ++sum[r-1];
		l/=2; r/=2;
	}
}
int GetBestPosition(int D, int C, int R, int *K, int *S, int *E) {
	n=D; m=C; k=R;
	while(N<n) N*=2;
	rep(i, N) tr[N+i]=1;
	rep(i, n-1) ma[N+i]=K[i];
	for(int i=N-1; i; --i) {
		tr[i]=tr[2*i]+tr[2*i+1];
		ma[i]=max(ma[2*i], ma[2*i+1]);
	}
	rep(i, m) {
		int l, r=znajdz(1, E[i]+1);
		if(S[i]==0) l=0;
		else l=znajdz(1, S[i])+1;
		if(cnt(l, r-1)<k) dodaj(l, r);
		upd(1, 0, N-1, l, r-1);
	}
	for(int i=1; i<N; ++i) {
		sum[2*i]+=sum[i];
		sum[2*i+1]+=sum[i];
	}
	pair<int,int>ans={-1, -1};
	rep(i, n) ans=max(ans, {sum[N+i], -i});
	return -ans.nd;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51