oj.uz

Submission #315864

# Submission time Handle Problem Language Result Execution time Memory
315864 2020-10-24T07:13:15 Z tengiz05 Jousting tournament (IOI12_tournament) C++17
100 / 100
 288 ms 22068 KB 
#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

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.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 10 ms 3744 KB Output is correct
3 Correct 7 ms 3200 KB Output is correct
4 Correct 10 ms 3456 KB Output is correct
5 Correct 10 ms 3456 KB Output is correct
6 Correct 10 ms 3328 KB Output is correct
7 Correct 10 ms 3584 KB Output is correct
8 Correct 10 ms 3456 KB Output is correct
9 Correct 7 ms 3200 KB Output is correct
10 Correct 12 ms 3456 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 8820 KB Output is correct
2 Correct 242 ms 22068 KB Output is correct
3 Correct 199 ms 13048 KB Output is correct
4 Correct 243 ms 17652 KB Output is correct
5 Correct 236 ms 18808 KB Output is correct
6 Correct 288 ms 14960 KB Output is correct
7 Correct 241 ms 19192 KB Output is correct
8 Correct 243 ms 19324 KB Output is correct
9 Correct 166 ms 12920 KB Output is correct
10 Correct 194 ms 13048 KB Output is correct