oj.uz

Submission #125619

# Submission time Handle Problem Language Result Execution time Memory
125619 2019-07-06T05:32:47 Z nxteru Jousting tournament (IOI12_tournament) C++14
100 / 100
 181 ms 12544 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 7 ms 5240 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Correct 6 ms 4984 KB Output is correct
6 Correct 7 ms 5116 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 5068 KB Output is correct
9 Correct 6 ms 4984 KB Output is correct
10 Correct 6 ms 4984 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5084 KB Output is correct
2 Correct 12 ms 5496 KB Output is correct
3 Correct 9 ms 5116 KB Output is correct
4 Correct 12 ms 5368 KB Output is correct
5 Correct 12 ms 5368 KB Output is correct
6 Correct 12 ms 5240 KB Output is correct
7 Correct 13 ms 5368 KB Output is correct
8 Correct 12 ms 5368 KB Output is correct
9 Correct 9 ms 5240 KB Output is correct
10 Correct 14 ms 5368 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7992 KB Output is correct
2 Correct 177 ms 12544 KB Output is correct
3 Correct 94 ms 7644 KB Output is correct
4 Correct 177 ms 12320 KB Output is correct
5 Correct 169 ms 12076 KB Output is correct
6 Correct 181 ms 10940 KB Output is correct
7 Correct 174 ms 12304 KB Output is correct
8 Correct 174 ms 12292 KB Output is correct
9 Correct 83 ms 7160 KB Output is correct
10 Correct 96 ms 7584 KB Output is correct