oj.uz

Submission #137536

# Submission time Handle Problem Language Result Execution time Memory
137536 2019-07-28T06:20:28 Z mohammedehab2002 Jousting tournament (IOI12_tournament) C++11
100 / 100
 672 ms 36240 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;
tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> t;
int stt[200005],ent[200005],ct,dp[20][200005],stree[800005];
vector<int> v[200005];
void dfs(int node)
{
	for (int i=1;i<20;i++)
	{
		if (dp[i-1][node]!=-1)
		dp[i][node]=dp[i-1][dp[i-1][node]];
	}
	stt[node]=++ct;
	for (int u:v[node])
	dfs(u);
	ent[node]=ct;
}
void update(int node,int st,int en,int idx,int val)
{
	if (st==en)
	stree[node]=val;
	else
	{
		int mid=(st+en)/2;
		if (st<=idx && idx<=mid)
		update(2*node,st,mid,idx,val);
		else
		update(2*node+1,mid+1,en,idx,val);
		stree[node]=(stree[2*node]&stree[2*node+1]);
	}
}
int query(int node,int st,int en,int l,int r)
{
	if (en<l || st>r || r<l)
	return 1;
	if (l<=st && en<=r)
	return stree[node];
	int mid=(st+en)/2;
	return (query(2*node,st,mid,l,r)&query(2*node+1,mid+1,en,l,r));
}
int get(int pos)
{
	int ans=0,cur=pos;
	for (int i=19;i>=0;i--)
	{
		if (dp[i][cur]!=-1 && query(1,1,ct,stt[dp[i][cur]],ent[dp[i][cur]]))
		{
			ans+=(1<<i);
			cur=dp[i][cur];
		}
	}
	return ans;
}
int GetBestPosition(int n,int c,int r,int *k,int *s,int *e)
{
	memset(dp,-1,sizeof(dp));
	for (int i=0;i<n;i++)
	t.insert({i,i});
	for (int i=0;i<c;i++)
	{
		int cnt=e[i]-s[i]+1,cur;
		for (auto it=t.find_by_order(s[i]);cnt;cnt--)
		{
			auto tmp=it;
			it++;
			cur=tmp->first;
			dp[0][tmp->second]=n+i;
			t.erase(tmp);
		}
		t.insert({cur,n+i});
	}
	for (int i=0;i<n+c-1;i++)
	v[dp[0][i]].push_back(i);
	dfs(n+c-1);
	for (int i=0;i<n+c;i++)
	update(1,1,ct,stt[i],1);
	for (int i=1;i<n;i++)
	update(1,1,ct,stt[i],(k[i-1]<r));
	int ans=get(0),pos=0;
	for (int i=1;i<n;i++)
	{
		update(1,1,ct,stt[i],1);
		update(1,1,ct,stt[i-1],(k[i-1]<r));
		if (get(i)>ans)
		{
			ans=get(i);
			pos=i;
		}
	}
	return pos;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 20728 KB Output is correct
2 Correct 19 ms 20732 KB Output is correct
3 Correct 21 ms 20728 KB Output is correct
4 Correct 21 ms 20728 KB Output is correct
5 Correct 20 ms 20728 KB Output is correct
6 Correct 21 ms 20728 KB Output is correct
7 Correct 24 ms 20728 KB Output is correct
8 Correct 21 ms 20700 KB Output is correct
9 Correct 24 ms 20728 KB Output is correct
10 Correct 24 ms 20860 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 20856 KB Output is correct
2 Correct 40 ms 21552 KB Output is correct
3 Correct 26 ms 21240 KB Output is correct
4 Correct 37 ms 21624 KB Output is correct
5 Correct 35 ms 21496 KB Output is correct
6 Correct 33 ms 21368 KB Output is correct
7 Correct 42 ms 21496 KB Output is correct
8 Correct 42 ms 21504 KB Output is correct
9 Correct 26 ms 21240 KB Output is correct
10 Correct 34 ms 21368 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 26744 KB Output is correct
2 Correct 660 ms 36240 KB Output is correct
3 Correct 268 ms 30072 KB Output is correct
4 Correct 623 ms 34408 KB Output is correct
5 Correct 663 ms 34808 KB Output is correct
6 Correct 416 ms 32484 KB Output is correct
7 Correct 639 ms 35012 KB Output is correct
8 Correct 672 ms 35064 KB Output is correct
9 Correct 256 ms 29856 KB Output is correct
10 Correct 298 ms 30044 KB Output is correct