Submission #315706

#	Time	Username	Problem	Language	Result	Execution time	Memory
315706		tengiz05	Jousting tournament (IOI12_tournament)	C++17	0 / 100	122 ms	10612 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;
bool used[N];
vector<int> edges[N];
int mxans=0, indans=0;
vector<pair<int, int>> temp;
bool cmp(pair<int, int> &f, pair<int, int> &s){
	if(f.second > s.second)return true;
	else if(f.second < s.second)return false;
	else {
		if(f.first < s.first)return true;
		else return false;
	}
}
void dfs(int u){
//	cout << u << ' ';
	used[u] = true;
	int ans = 0;
	for(auto v : edges[u]){
		if(used[v])continue;
		dfs(v);
		ans = max(ans, dp[v]);
	}
	int l = temp[u].first, r = temp[u].second;
	if(k[l] == k[r-1])dp[u] = ans+1;
	else dp[u] = ans;
	if(dp[u] > mxans){
		mxans = dp[u];
		indans = u;
	}//cout << l << ' ' << r << '\n';
}
int GetBestPosition(int NN, int C, int R, int *K, int *S, int *E) {
	n = NN, m = C;
	ordered_set<int> s1, s2;
	for(int i=0;i<n;i++)s1.insert(i), s2.insert(i);
	for(int i=0;i<n;i++){
		if(K[i] > R)k[i] = 1;
		else k[i] = 0;
		if(i)k[i] += k[i-1];
	}//cout << '\n';
	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));
	/*	for(auto x : s1){
			cout << x << ' ';}cout << "\n\n";*/
		temp.push_back({l, r});
	}
	sort(temp.begin(), temp.end(), cmp);
/*	for(auto X : temp){
		cout << X.first << ' ' << X.second << '\n';
	}*/
	int u = 0;
	int l=temp[0].first, r=temp[0].second,i=1;
	while(i < temp.size()){
		auto x = temp[i];
		if(x.first > r || x.second < l){
			u = par[u];
			continue;
		}
		edges[u].push_back(i);
		edges[i].push_back(u);
		par[i] = u;u=i;
		i++;
	}
	dfs(0);
	return indans;
}
/*

5 3 3
1
0
2
4
1 3
0 1
0 1

*/

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:64: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]
   64 |  while(i < temp.size()){
      |        ~~^~~~~~~~~~~~~

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