oj.uz

Submission #94106

# Submission time Handle Problem Language Result Execution time Memory
94106 2019-01-16T06:00:27 Z fjzzq2002 Jousting tournament (IOI12_tournament) C++14
100 / 100
 182 ms 31984 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T>
struct rbt: tree<T,int,less<T>,
rb_tree_tag,tree_order_statistics_node_update>{};
typedef pair<int,int> pii;
#define fi first
#define se second
#define SZ 666666
rbt<pii> s; int fa[SZ];
pii gs[SZ]; int gn=0,su[SZ];
vector<int> ch[SZ];
pii ans(-1,0);
void dfs(int t,int d=0,int s=0)
{
	s+=(su[gs[t].se]-su[gs[t].fi]==0);
	if(gs[t].fi==gs[t].se)
		ans=max(ans,pii(s-1,-gs[t].fi));
	for(auto c:ch[t]) dfs(c,d+1,s);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
	gn=0; ans=pii(-1,0); s.clear();
	for(int i=0;i<N;++i)
		gs[++gn]=pii(i,i),
		fa[gn]=0,ch[gn].clear(),
		s[pii(i,i)]=gn;
	for(int i=0;i<N-1;++i)
		su[i+1]=su[i]+(K[i]>=R);
	for(int i=0;i<C;++i)
	{
		auto g=s.find_by_order(S[i]);
		int L=g->fi.fi,R; ++gn;
		fa[gn]=0; ch[gn].clear();
		for(int j=1;j<=E[i]-S[i]+1;++j)
			R=g->fi.se,fa[g->se]=gn,
			ch[gn].push_back(g->se),
			s.erase(g++);
		gs[gn]=pii(L,R);
		s[pii(L,R)]=gn;
	}
	dfs(gn); return -ans.se;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 15992 KB Output is correct
2 Correct 13 ms 15992 KB Output is correct
3 Correct 14 ms 16120 KB Output is correct
4 Correct 13 ms 16120 KB Output is correct
5 Correct 16 ms 15992 KB Output is correct
6 Correct 15 ms 15992 KB Output is correct
7 Correct 16 ms 15992 KB Output is correct
8 Correct 13 ms 15992 KB Output is correct
9 Correct 13 ms 15992 KB Output is correct
10 Correct 13 ms 15992 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16120 KB Output is correct
2 Correct 20 ms 16804 KB Output is correct
3 Correct 16 ms 16504 KB Output is correct
4 Correct 18 ms 16632 KB Output is correct
5 Correct 18 ms 16760 KB Output is correct
6 Correct 20 ms 16632 KB Output is correct
7 Correct 18 ms 16760 KB Output is correct
8 Correct 18 ms 16704 KB Output is correct
9 Correct 16 ms 16376 KB Output is correct
10 Correct 20 ms 16632 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 20792 KB Output is correct
2 Correct 182 ms 31984 KB Output is correct
3 Correct 112 ms 25080 KB Output is correct
4 Correct 168 ms 29432 KB Output is correct
5 Correct 169 ms 30216 KB Output is correct
6 Correct 180 ms 26652 KB Output is correct
7 Correct 172 ms 30200 KB Output is correct
8 Correct 174 ms 30328 KB Output is correct
9 Correct 87 ms 24824 KB Output is correct
10 Correct 114 ms 25080 KB Output is correct