Submission #315864

#	Time	Username	Problem	Language	Result	Execution time	Memory
315864		tengiz05	Jousting tournament (IOI12_tournament)	C++17	100 / 100	288 ms	22068 KiB

tournament

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
//order_of_key(x) = position of element x;
//find_by_order(i) = a[i];
const int N = 1e5+5;
int dp[N], k[N], par[N], n, m, mn[N];
bool used[N];
vector<int> edges[N];
int mxans=-1, indans;
vector<pair<int, int>> temp;
bool cmp(pair<int, int> &f, pair<int, int> &s){
	if(f.first == s.first)return f.second > s.second;
	return f.first < s.first;
}
void dfs(int u){
	used[u] = true;
	int ans = 0;
	int Min = temp[u].first;
	for(auto v : edges[u]){
		if(used[v])continue;
		dfs(v);
		if(ans < dp[v]){
			ans = dp[v];
			Min = mn[v];
		}
	}int l = temp[u].first, r = temp[u].second;
	if(k[l] == k[r])dp[u] = ans+1;
	else dp[u] = ans;
	mn[u] = Min;
}
int GetBestPosition(int NN, int C, int R, int *K, int *S, int *E) {
	n = NN, m = C;indans=n-1;
	ordered_set<int> s1, s2;
	for(int i=0;i<n;i++)s1.insert(i), s2.insert(i);
	for(int i=1;i<n;i++){
		if(K[i-1] > R)k[i] = 1;
		else k[i] = 0;
		if(i)k[i] += k[i-1];
	}
	for(int i=0;i<m;i++){
		int l = *s1.find_by_order(S[i]);
		int r = *s2.find_by_order(E[i]);
		for(int j=0;j<E[i]-S[i];j++)s1.erase(s1.find_by_order(S[i]+1));
		for(int j=0;j<E[i]-S[i];j++)s2.erase(s2.find_by_order(S[i]+0));
		temp.push_back({l, r});
	}
	sort(temp.begin(), temp.end(), cmp);
	int u = 0;
	int l, r, i=1;
	while(i < temp.size()){
		l=temp[u].first, r=temp[u].second;
		auto x = temp[i];
		while(x.first > r || x.second < l){
			u = par[u];
			l = temp[u].first, r=temp[u].second;
		}
		edges[u].push_back(i);
		edges[i].push_back(u);
		par[i] = u;u=i;
		i++;
	}
	dfs(0);
	return mn[0];
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:54:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  while(i < temp.size()){
      |        ~~^~~~~~~~~~~~~

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