Submission #125619

#	Time	Username	Problem	Language	Result	Execution time	Memory
125619		nxteru	Jousting tournament (IOI12_tournament)	C++14	100 / 100	181 ms	12544 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
struct BIT{
	int n,bit[100005];
	void ini(int x){
		n=x;
		for(int i=0;i<=n;i++)bit[i]=0;
	}
	void add(int a,int x){
		a++;
		while(a<=n){
			bit[a]+=x;
			a+=(a&-a);
		}
	}
	int sum(int a){
		int res=0;
		a++;
		while(a>0){
			res+=bit[a];
			a-=(a&-a);
		}
		return res;
	}
	int serch(int x){
		int l=-1,r=n-1;
		while(r-l>1){
			int m=(l+r)/2;
			if(sum(m)>=x)r=m;
			else l=m;
		}
		return r;
	}
};
int n,m,ans,rst[100005],in;
vector<int>f[100005],t[100005];
bool lo[100005],ro[100005];
BIT bit1,bit2;
int GetBestPosition(int N, int C, int p, int *c, int *a, int *b) {
	n=N,m=C;
	bit1.ini(n);
	bit2.ini(n);
	for(int i=1;i<n;i++)bit1.add(i,1),bit2.add(i,1);
	for(int i=0;i<m;i++){
		int x=a[i],y=b[i];
		a[i]=bit1.serch(a[i]);
		b[i]=bit2.serch(b[i]);
		for(int i=y;i>x;i--)bit1.add(bit1.serch(i),-1);
		for(int i=y-1;i>=x;i--)bit2.add(bit2.serch(i),-1);
		f[a[i]].PB(i);
		t[b[i]].PB(i);
	}
	int l=-1,r=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<f[i].size();j++){
			int x=f[i][j];
			if(ro[x])in++;
			lo[x]=true;
		}
		while(r<n&&(r<=i||c[r-1]<=p)){
			for(int j=0;j<t[r].size();j++){
				int x=t[r][j];
				if(lo[x])in++;
				ro[x]=true;
			}
			r++;
		}
		rst[i]=in;
		if(in>rst[ans])ans=i;
		for(int j=0;j<t[i].size();j++){
			int x=t[i][j];
			if(lo[x])in--;
			ro[x]=false;
		}
		if(i<n-1&&c[i]>p){
			while(l<i){
				l++;
				for(int j=0;j<f[l].size();j++){
					int x=f[l][j];
					if(ro[x])in--;
					lo[x]=false;
				}
			}
		}
	}
	return ans;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<f[i].size();j++){
               ~^~~~~~~~~~~~
tournament.cpp:62:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<t[r].size();j++){
                ~^~~~~~~~~~~~
tournament.cpp:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<t[i].size();j++){
               ~^~~~~~~~~~~~
tournament.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<f[l].size();j++){
                 ~^~~~~~~~~~~~

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