Submission #804270

# Submission time Handle Problem Language Result Execution time Memory
804270 2023-08-03T07:43:53 Z dungz Kralj (COCI16_kralj) C++17
56 / 140
2000 ms 64848 KB
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
vector<int> f[500005];
int n,st2;
int pos[500005];
int val[500005];
set<int> fuck,fuck2;
int con(ll x){
	int temp=x%n;
	if(temp==0) return n;
	else return temp;
}
int main(){
	// #ifndef ONLINE_JUDGE
   	// 	freopen (task".inp", "r", stdin);
   	// 	freopen (task".out", "w", stdout);
	// #endif
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>pos[i];
		st2=pos[i];
	}	
	for(int i=1;i<=n;i++)
	{
		cin>>val[i];
	}
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		f[pos[i]].push_back(x);
	}
	int st=st2;
	int ed=st2;
	int rem=f[st2].size()-1;
	st2=con(st2+1);
	while(st2!=ed)
	{
		rem+=f[st2].size()-1;
		if(rem<0)
		{
			st=-1;
			rem=0;
		}
		else if(st==-1)
		{
			st=st2;
		}
		st2=con(st2+1);
	}
	ed=st;
	fuck.insert(val[st]);
	for(auto i:f[st]) fuck2.insert(i);
	int ans=0,dem=1;
	st=con(st+1);
	while(st!=ed)
	{
		if(f[st].size()!=0)
		{
			for(auto i:fuck)
			{
				auto pos=fuck2.lower_bound(i);
				if(pos!=fuck2.end())
				{
					dem--;
					ans+=1;
					fuck2.erase(pos);
				}
			}
			while(dem)
			{
				fuck2.erase(fuck2.begin());
				dem--;
			}
			dem=0;
		}
		for(auto i:f[st]) fuck2.insert(i);
		fuck.insert(val[st]);
		dem++;
		st=con(st+1);
	}
	for(auto i:fuck)
	{
		auto pos=fuck2.lower_bound(i);
		if(pos!=fuck2.end())
		{
			ans+=1;
			fuck2.erase(pos);
		}
	}
	cout<<ans;
}
/*

*/
# Verdict Execution time Memory Grader output
1 Correct 478 ms 54400 KB Output is correct
2 Correct 496 ms 53396 KB Output is correct
3 Correct 672 ms 63512 KB Output is correct
4 Correct 748 ms 64848 KB Output is correct
5 Execution timed out 2066 ms 18892 KB Time limit exceeded
6 Execution timed out 2049 ms 19232 KB Time limit exceeded
7 Execution timed out 2019 ms 21876 KB Time limit exceeded
8 Execution timed out 2068 ms 21756 KB Time limit exceeded
9 Execution timed out 2055 ms 22376 KB Time limit exceeded
10 Execution timed out 2055 ms 19912 KB Time limit exceeded