oj.uz

Submission #315861

# Submission time Handle Problem Language Result Execution time Memory
315861 2020-10-24T07:10:57 Z tengiz05 Jousting tournament (IOI12_tournament) C++17
100 / 100
 107 ms 17260 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int dp[N], k[N], par[N], n, m, mn[N];
bool used[N];
vector<int> edges[N];
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){
//	cout << u << '\n';
	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;
}
struct segtree {
	vector<int> t;
	int sz;
	void build(){
		sz=1;
		while(sz <= n)sz<<=1;
		t.assign(sz*2,1);
		for(int i=sz-1;i>0;i--)t[i] = t[i*2]+t[i*2+1];
	}
	void update(int l, int r, int L, int R, int node){
		if(L >= r || R <= l)return;
		if(L >= l && R <= r){
			t[node] = 0;
			return;
		}int mid = (L+R)/2;
		update(l, r, L, mid, node*2);
		update(l, r, mid, R, node*2+1);
		t[node] = t[node*2]+t[node*2+1];
	}void update(int l, int r){update(l, r+1, 0, sz, 1);}
	
	int get(int k, int L, int R, int node){
		if(R-L==1)return L;
		int mid = (L+R)/2;
		if(t[node*2] >= k)return get(k, L,mid, node*2);
		else return get(k-t[node*2], mid,R, node*2+1);
	}int get(int k){return get(k+1, 0, sz, 1);}
}seg;
int GetBestPosition(int NN, int C, int R, int *K, int *S, int *E) {
	n = NN, m = C;
	seg.build();
	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 = seg.get(S[i]);
		int r = seg.get(E[i]+1);r--;
		seg.update(l+1, r);
		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, 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);//for(int i=0;i<3;i++)cout << dp[i] << ';';cout << '\n';
	return mn[0];
}
/*

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

*/

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:76: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]
   76 |  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 2 ms 2688 KB Output is correct
7 Correct 3 ms 2688 KB Output is correct
8 Correct 3 ms 2728 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 2688 KB Output is correct
2 Correct 6 ms 3456 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 6 ms 3200 KB Output is correct
5 Correct 6 ms 3200 KB Output is correct
6 Correct 5 ms 2944 KB Output is correct
7 Correct 6 ms 3328 KB Output is correct
8 Correct 6 ms 3200 KB Output is correct
9 Correct 3 ms 2816 KB Output is correct
10 Correct 8 ms 3072 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5436 KB Output is correct
2 Correct 102 ms 17260 KB Output is correct
3 Correct 22 ms 4864 KB Output is correct
4 Correct 104 ms 12912 KB Output is correct
5 Correct 100 ms 14316 KB Output is correct
6 Correct 78 ms 8176 KB Output is correct
7 Correct 102 ms 14448 KB Output is correct
8 Correct 107 ms 14396 KB Output is correct
9 Correct 18 ms 4480 KB Output is correct
10 Correct 22 ms 4728 KB Output is correct