oj.uz

Submission #242292

# Submission time Handle Problem Language Result Execution time Memory
242292 2020-06-27T08:22:05 Z errorgorn Jousting tournament (IOI12_tournament) C++14
100 / 100
 466 ms 51700 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	int val=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int j){
		if (s==e) val=j;
		else{
			if (i<=m) l->update(i,j);
			else r->update(i,j);
			
			val=max(l->val,r->val);
		}
	}
	
	int query(int i,int j){
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return max(l->query(i,m),r->query(m+1,j));
	}
} *root=new node(0,100005);

struct node2{
	int s,e,m;
	int val=0;
	node2 *l,*r;
	
	node2 (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node2(s,m);
			r=new node2(m+1,e);
		}
	}
	
	void update(int i,int j,int k){
		if (s==i && e==j) val+=k;
		else if (j<=m) l->update(i,j,k);
		else if (m<i) r->update(i,j,k);
		else l->update(i,m,k),r->update(m+1,j,k);
	}
	
	int query(int i){
		if (s==e) return val;
		else if (i<=m) return val+l->query(i);
		else return val+r->query(i);
	}
} *root2=new node2(0,100005);

struct node3{ //fucking end me stupid pbds erase dont work
	int s,e,m;
	int val=0;
	node3 *l,*r;
	
	node3 (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node3(s,m);
			r=new node3(m+1,e);
		}
	}
	
	void update(int i,int j){
		val+=j;
		if (s!=e){
			if (i<=m) l->update(i,j);
			else r->update(i,j);
		}
	}
	
	int query(int i){
		if (s==e) return s;
		else if (l->val<=i) return r->query(i-l->val);
		else return l->query(i);
	}
} *root3=new node3(0,100005);

int n,m,late;
int ranks[100005];

ii rounds[100005];


//tournament tree stuff
int curr[100005]; //which nodes this refers to

ii range[200005];
int parent[200005][20]; //2k decomp here

//knight pos
int best[100005]; //what is the best (latest) round the late guy goes

//final stuff
vector<int> proc; //process in order of latest round late guy goes

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	n=N,m=C,late=R;
	
	rep(x,0,n-1){
		ranks[x]=K[x];
	}
	rep(x,0,m) rounds[x]={S[x],E[x]};
	
	//build tournament tree
	memset(parent,-1,sizeof(parent));
	rep(x,0,n){
		curr[x]=x;
		range[x]={x,x};
		root3->update(x,1);
	}
	
	int IDX=n; //new nodes index
	rep(x,0,m){
		range[IDX]={1e9,-1e9};
		
		rep(y,rounds[x].fi,rounds[x].se+1){
			//cout<<root3->query(y)<<" ";
			
			int temp=curr[root3->query(y)];
			
			parent[temp][0]=IDX;
			range[IDX]={min(range[IDX].fi,range[temp].fi),max(range[IDX].se,range[temp].se)};
		}
		//cout<<endl;
		
		rep(y,0,rounds[x].se-rounds[x].fi){
			root3->update(root3->query(rounds[x].fi),-1);
		}
		curr[root3->query(rounds[x].fi)]=IDX++;
	}
	
	rep(x,IDX,0){
		int curr=parent[x][0];
		
		rep(level,0,20){
			if (curr==-1) break;
			curr=parent[x][level+1]=parent[curr][level];
		}
	}
	
	//rep(x,0,IDX) cout<<range[x].fi<<" "<<range[x].se<<" "<<parent[x][0]<<" "<<parent[x][1]<<endl;
	
	//simulate everything
	root->update(0,late);
	rep(x,0,n-1){
		root->update(x+1,ranks[x]);
	}
	
	rep(x,0,n){
		int curr=x;
		
		rep(x,20,0) if (parent[curr][x]!=-1){
			if (root->query(range[parent[curr][x]].fi,range[parent[curr][x]].se)<=late) curr=parent[curr][x];
		}
		
		best[x]=curr;
		
		root->update(x,ranks[x]);
		root->update(x+1,late);
	}
	
	//rep(x,0,n) cout<<best[x]<<" ";cout<<endl;
	
	rep(x,0,n) proc.push_back(x);
	
	sort(all(proc),[](int i,int j){
		return best[i]<best[j];
	});
	
	int curr=-1;
	int most=0;
	int ans=-1;
	for (auto &it:proc){
		while (curr<best[it]){
			curr++;
			root2->update(range[curr].fi,range[curr].se,1);
		}
		
		int temp=root2->query(it);
		if (most<temp || (most==temp && it<ans)){
			most=temp;
			ans=it;
		}
	}
	
	return ans;
}

Compilation message

tournament.cpp: In constructor 'node::node(int, int)':
tournament.cpp:40:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~
tournament.cpp: In constructor 'node2::node2(int, int)':
tournament.cpp:72:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~
tournament.cpp: In constructor 'node3::node3(int, int)':
tournament.cpp:100:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   s=_s,e=_e,m=s+e>>1;
               ~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 44156 KB Output is correct
2 Correct 43 ms 44152 KB Output is correct
3 Correct 41 ms 44152 KB Output is correct
4 Correct 41 ms 44280 KB Output is correct
5 Correct 42 ms 44152 KB Output is correct
6 Correct 42 ms 44152 KB Output is correct
7 Correct 42 ms 44152 KB Output is correct
8 Correct 44 ms 44288 KB Output is correct
9 Correct 41 ms 44160 KB Output is correct
10 Correct 40 ms 44152 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 44280 KB Output is correct
2 Correct 56 ms 44536 KB Output is correct
3 Correct 46 ms 44412 KB Output is correct
4 Correct 57 ms 44536 KB Output is correct
5 Correct 52 ms 44536 KB Output is correct
6 Correct 48 ms 44516 KB Output is correct
7 Correct 56 ms 44536 KB Output is correct
8 Correct 56 ms 44540 KB Output is correct
9 Correct 45 ms 44408 KB Output is correct
10 Correct 54 ms 44536 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 47480 KB Output is correct
2 Correct 466 ms 51700 KB Output is correct
3 Correct 188 ms 48160 KB Output is correct
4 Correct 416 ms 51700 KB Output is correct
5 Correct 423 ms 51472 KB Output is correct
6 Correct 280 ms 50420 KB Output is correct
7 Correct 455 ms 51700 KB Output is correct
8 Correct 437 ms 51676 KB Output is correct
9 Correct 174 ms 47988 KB Output is correct
10 Correct 211 ms 48116 KB Output is correct