oj.uz

Submission #349854

# Submission time Handle Problem Language Result Execution time Memory
349854 2021-01-18T14:17:32 Z Kerim Jousting tournament (IOI12_tournament) C++17
100 / 100
 293 ms 31980 KB 
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int,int> PII;
typedef tree<PII,null_type,less<PII>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int id=-1,P[MAXN][18];
vector<int>adj[MAXN];
ordered_set s;
int in[MAXN],out[MAXN],T;
void add(int x,int y){
	P[y][0]=x;adj[x].pb(y);	
}
void dfs(int nd){
	in[nd]=++T;
	tr(it,adj[nd])dfs(*it);
	out[nd]=T;
}	
int F[MAXN];
void upd(int x,int val){
	for(;x<MAXN;x+=x&(-x))F[x]+=val;
}
int get(int x){
	int res=0;
	for(;x;x-=x&(-x))
		res+=F[x];
	return res;	
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	for(int i=0;i<N;i++)s.insert(mp(i,i)),id++;
	for(int i=0;i<C;i++){
		__typeof((s).begin())it=s.find_by_order(S[i]);
		int who=it->ff;id++;
		for(int j=0;j<=E[i]-S[i];j++)
			add(id,it->ss),s.erase(it++);
		s.insert(mp(who,id));
	}
	for(int j=1;j<18;j++)
		for(int i=0;i<=id;i++)
			if(P[i][j-1])
				P[i][j]=P[P[i][j-1]][j-1];
	dfs(id);
	for(int i=1;i<N;i++)
		upd(in[i],(K[i-1]>R));	
	int res=-1,who;
	for(int i=0;i<N;i++){
		int ans=0,nd=i;
		for(int j=17;j>=0;j--)	
			if(P[nd][j] and get(out[P[nd][j]])==get(in[P[nd][j]]-1))
				nd=P[nd][j],ans+=(1<<j);
		if(i+1<N){
			upd(in[i+1],-(K[i]>R));
			upd(in[i],(K[i]>R));	
		}
		if(umax(res,ans))who=i;
	}
  	return who;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:73:11: warning: 'who' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |    return who;
      |           ^~~

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5228 KB Output is correct
2 Correct 12 ms 6380 KB Output is correct
3 Correct 8 ms 5868 KB Output is correct
4 Correct 12 ms 6380 KB Output is correct
5 Correct 11 ms 6272 KB Output is correct
6 Correct 11 ms 6124 KB Output is correct
7 Correct 12 ms 6380 KB Output is correct
8 Correct 12 ms 6380 KB Output is correct
9 Correct 8 ms 5740 KB Output is correct
10 Correct 13 ms 6380 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 15416 KB Output is correct
2 Correct 293 ms 31468 KB Output is correct
3 Correct 138 ms 21200 KB Output is correct
4 Correct 285 ms 31300 KB Output is correct
5 Correct 274 ms 31084 KB Output is correct
6 Correct 239 ms 26732 KB Output is correct
7 Correct 280 ms 31980 KB Output is correct
8 Correct 285 ms 31852 KB Output is correct
9 Correct 119 ms 20460 KB Output is correct
10 Correct 143 ms 21100 KB Output is correct