Submission #1261804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261804		PlayVoltz	Jousting tournament (IOI12_tournament)	C++20	0 / 100	0 ms	324 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

struct fen{
	int n;
	vector<int> ftt;
	fen(int N){
		n=N;
		ftt.resize(n+1, 0);
	}
	void up(int i, int v){
		for (;i<=n;i+=i&-i)ftt[i]+=v;
	}
	int sum(int i){
		int res=0;
		for (int p=i;p;p-=p&-p)res+=ftt[p];
		return res;
	}
	int bs(int v){
		int res=n, id=0, sum=0;
		for (int i=20; i>=0; --i)if (id+(1<<i)<=n){
			if (sum+ftt[id+(1<<i)]>=v)res=id+(1<<i);
			else id+=(1<<i), sum+=ftt[id];
		}
		return res;
	}
}*ft;

int GetBestPosition(int n, int q, int k, int *K, int *L, int *R){
	vector<int> vect(n+1), psum(n+2, 0), p(n+1, 1), d(n+2, 0);
	ft = new fen(n);
	for (int i=1; i<n; ++i)vect[i]=K[i-1];
	for (int i=1; i<=n; ++i){
		psum[i+1]=psum[i]+(vect[i]>k);
		ft->up(i, 1);
		p[i]=i+1;
	}
	for (int i=0; i<q; ++i){
		int l=ft->bs(L[i]+1), r=ft->bs(R[i]+1);
		for (int j=l+1; j<=r; j=p[j])ft->up(j, -1);
		p[l]=r+1;
		if (psum[l]==psum[r])++d[l], --d[r+1];
	}
	int mx=0, best=0;
	for (int i=1, sum=0; i<=n; ++i){
		sum+=d[i];
		if (sum>mx)mx=sum, best=i-1;
	}
	return best;
}

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