oj.uz

Submission #402053

# Submission time Handle Problem Language Result Execution time Memory
402053 2021-05-11T08:52:36 Z Jasiekstrz Jousting tournament (IOI12_tournament) C++17
100 / 100
 218 ms 23632 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
const int NN=1e5;
const int L=17;
int d[NN+10];
tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> st;
int mx[L+2][2][NN+10];
void build_rmq(int N,int *K)
{
	for(int rot:{1,0})
	{
		for(int i=0;i<N-1;i++)
		{
			mx[0][rot][i]=K[i];
			for(int j=1;j<=L;j++)
			{
				if(i-(1<<(j-1))<0)
					mx[j][rot][i]=mx[j-1][rot][i];
				else
					mx[j][rot][i]=max(mx[j-1][rot][i],mx[j-1][rot][i-(1<<(j-1))]);
			}
		}
		reverse(K,K+N-1);
		for(int j=0;j<=L;j++)
		{
			reverse(mx[j][0],mx[j][0]+N-1);
			reverse(mx[j][1],mx[j][1]+N-1);
		}
	}
	return;
}
int get_max(int l,int r)
{
	int lg=__lg(r-l+1);
	return max(mx[lg][0][l],mx[lg][1][r]);
}
void add_interval(int l,int r,int R)
{
	if(l==r || get_max(l,r-1)<R)
	{
		d[l]++;
		d[r+1]--;
	}
	return;
}
int GetBestPosition(int N,int C,int R,int *K,int *S,int *E)
{
	build_rmq(N,K);
	for(int i=0;i<N;i++)
		st.insert(make_pair(i,i));
	for(int i=0;i<C;i++)
	{
		auto s=(*st.find_by_order(S[i])),e=(*st.find_by_order(E[i]));
		add_interval(s.fi,e.se,R);
		st.erase(s);
		st.insert(make_pair(s.fi,e.se));
		for(int j=E[i];j>S[i];j--)
			st.erase(st.find_by_order(j));
	}
	int ans=0,bst=0;
	int curr=0;
	for(int i=0;i<N;i++)
	{
		curr+=d[i];
		if(curr>ans)
		{
			ans=curr;
			bst=i;
		}
	}
	return bst;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Output is correct
2 Correct 7 ms 1484 KB Output is correct
3 Correct 5 ms 1484 KB Output is correct
4 Correct 8 ms 1592 KB Output is correct
5 Correct 7 ms 1484 KB Output is correct
6 Correct 8 ms 1568 KB Output is correct
7 Correct 7 ms 1484 KB Output is correct
8 Correct 7 ms 1484 KB Output is correct
9 Correct 5 ms 1484 KB Output is correct
10 Correct 9 ms 1608 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 11684 KB Output is correct
2 Correct 217 ms 22832 KB Output is correct
3 Correct 136 ms 21828 KB Output is correct
4 Correct 202 ms 23632 KB Output is correct
5 Correct 204 ms 22804 KB Output is correct
6 Correct 218 ms 23188 KB Output is correct
7 Correct 207 ms 23536 KB Output is correct
8 Correct 217 ms 23588 KB Output is correct
9 Correct 123 ms 21572 KB Output is correct
10 Correct 136 ms 21924 KB Output is correct