oj.uz

Submission #289949

# Submission time Handle Problem Language Result Execution time Memory
289949 2020-09-03T09:01:39 Z emanIaicepsa Jousting tournament (IOI12_tournament) C++14
100 / 100
 253 ms 18144 KB 
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define mem(x,i) memset(x,i,sizeof(x))
#define dbg(x) cerr<<#x<<" = "<<x<<'\n';
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
using namespace std;
using namespace __gnu_pbds;
tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> tr;

vector<pii> in[100005], out[100005];
int seg[200005];

void build(int N,int *K){
	for(int i=N;i<2*N;i++) seg[i] = K[i-N];
	for(int i=N-1;i>0;i--) seg[i] = max(seg[i*2], seg[i*2+1]);
}

int query(int N,int l,int r){
	int ans = -1;
	for(l+=N,r+=N+1;l<r;l>>=1,r>>=1){
		if(l&1) ans = max(ans, seg[l++]);
		if(r&1) ans = max(ans, seg[--r]);
	}
	return ans;
}

int cnt[100005];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	for(int i=0;i<N;i++) tr.insert({i,i});
	build(N-1,K);
	for(int i=0;i<C;i++){
		auto fr = tr.find_by_order(S[i]), ba = tr.find_by_order(E[i]);
		int L = fr->fi, R = ba->se;
		auto iter = fr;
		while(iter != ba) iter = tr.erase(iter);
		tr.erase(iter);
		tr.insert({L,R});
		S[i] = L, E[i] = R;
		int rmq = query(N-1,S[i],E[i]-1);
		in[S[i]].pb(rmq,++cnt[rmq]);
		out[E[i]+1].pb(rmq,cnt[rmq]);
		//cout<<S[i]<<" "<<E[i]<<" "<<rmq<<'\n';
	}
	tr.clear();
	int ans = 0, mx = 0;
	for(int i=0;i<N;i++){
		for(auto x:in[i]) tr.insert(x);
		for(auto x:out[i]) tr.erase(x);
		int rk = tr.order_of_key({R,0});
		//cout<<i<<" "<<rk<<'\n';
		if(rk > mx){
			mx = rk;
			ans = i;
		}
	}
	return ans;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 14 ms 5632 KB Output is correct
3 Correct 7 ms 5504 KB Output is correct
4 Correct 12 ms 5632 KB Output is correct
5 Correct 11 ms 5632 KB Output is correct
6 Correct 10 ms 5632 KB Output is correct
7 Correct 12 ms 5632 KB Output is correct
8 Correct 11 ms 5632 KB Output is correct
9 Correct 7 ms 5376 KB Output is correct
10 Correct 13 ms 5632 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 9848 KB Output is correct
2 Correct 253 ms 18144 KB Output is correct
3 Correct 116 ms 13560 KB Output is correct
4 Correct 242 ms 15352 KB Output is correct
5 Correct 231 ms 15736 KB Output is correct
6 Correct 243 ms 14688 KB Output is correct
7 Correct 248 ms 15864 KB Output is correct
8 Correct 239 ms 15864 KB Output is correct
9 Correct 93 ms 13176 KB Output is correct
10 Correct 125 ms 13560 KB Output is correct