Submission #1138523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138523		LCJLY	Jousting tournament (IOI12_tournament)	C++20	0 / 100	2 ms	2888 KiB

tournament

#include <bits/stdc++.h>
#include <bits/extc++.h>
//#include "grader.cpp"
using namespace std;
using namespace __gnu_pbds;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

template <typename T>
using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename K, typename V>
using pbds_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

vector<int>adj[100005];
bool notake[100005];
int d[100005];
int two[20][100005];

void dfs(int index, int par){
	for(int x=0;x<18;x++){
		if(two[x][index]==0) continue;
		two[x+1][index]=two[x][two[x][index]];
	}
	for(auto it:adj[index]){
		if(it==par) continue;
		d[it]=d[index]+1;
		two[0][it]=index;
		dfs(it,index);
		notake[index]|=notake[it];
	}
}

int32_t GetBestPosition(int32_t n, int32_t c, int32_t r, int32_t *k, int32_t *s, int32_t *e){
	pii range[c];
	pbds_set<int>se,se2;
	for(int x=0;x<n;x++){
		se.insert(x);
		se2.insert(x);
	}
	
	vector<int>storage[n+5];
	vector<int>storage2[n+5];
	for(int x=0;x<c;x++){
		int a=s[x];
		int b=e[x];
		if(a==0) range[x].first=0;
		else range[x].first=*se2.find_by_order(a-1)+1;
		if(b==(int)se.size()-1) range[x].second=n-1;
		else range[x].second=*se.find_by_order(b+1)-1;
		for(int y=b;y>a;y--){
			se.erase(*se.find_by_order(y));
		}
		for(int y=b-1;y>=a;y--){
			se2.erase(*se2.find_by_order(y));
		}
		storage[range[x].first].push_back(x);
		storage2[range[x].second+1].push_back(x);
	}
	
	int prefix[n+5];
	int counter=0;
	set<pii>take;
	for(int x=0;x<n-1;x++){
		//cout << k[x] << " ";
		if(k[x]>=r){
			counter++;
		}
		prefix[x]=counter;
	}
	//cout << "\n";
	
	//show(r,r);
	
	for(int x=0;x<c;x++){
		while(1){
			auto it=take.lower_bound({range[x].first,0});
			if(it==take.end()||range[it->second].first>range[x].second) break;
			adj[x].push_back(it->second);
			adj[it->second].push_back(x);
			take.erase(take.find(*it));
		}
		take.insert({range[x].first,x});
		
		//cout << range[x].first << " " << range[x].second << " range\n";
		
		int cnt=prefix[range[x].second-1];
		if(range[x].first>0) cnt-=prefix[range[x].first-1];
		if(cnt){
			notake[x]=true;
			//cout << "trigger\n";
		}
	}
	
	dfs(c-1,-1);
	set<pair<pii,int>>se3;
	pii best={-1,-1};
	for(int x=0;x<n;x++){
		for(auto it:storage[x]){
			//add maximise l, minimise r, index
			pii hold=range[it];
			se3.insert({{-hold.first,hold.second},it});
		}
		for(auto it:storage2[x]){
			//add maximise l, minimise r, index
			pii hold=range[it];
			se3.erase({{-hold.first,hold.second},it});
		}
		pair<pii,int>temp=*se3.begin();
		if(notake[temp.second]) continue;
		int cur=temp.second;
		for(int y=18;y>=0;y--){
			if(two[y][cur]==0) continue;
			if(notake[two[y][cur]]) continue;
			cur=two[y][cur];
		}
		//cout << d[temp.second]-d[cur]+1 << "\n";
		//best=max(best,{d[temp.second]-d[cur]+1,x});
		if(d[temp.second]-d[cur]+1>best.first){
			best.first=d[temp.second]-d[cur]+1;
			best.second=x;
		}
	}
	return best.second;
}

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