Submission #623422

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
623422	2022-08-05T14:50:51 Z	inksamurai	Kralj (COCI16_kralj)	C++17	140 / 140	958 ms	43288 KB

kralj

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3SgiE60 ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

signed main(){
_3SgiE60;
	int n;
	cin>>n;
	vi a(n);
	rep(i,n){
		cin>>a[i];
	}
	vi b(n);
	rep(i,n){
		cin>>b[i];
	}
	vi c(n);
	rep(i,n){
		cin>>c[i];
	}
	vec(vi) rbts(n);
	rep(i,n){
		a[i]-=1;
		// print(c[i]);
		rbts[a[i]].pb(c[i]);
	}
	vec(pii) evs;
	rep(i,n){
		int l=i;
		int now=sz(rbts[i]);
		while(now>1){
			now-=1;
			l+=1;
			now+=sz(rbts[l%n]);
		}
		evs.pb(pii(i,l));
		if(l>n){
			break;
		}else{
			i=l;
		}
	}
	int r=-1;
	{
		for(auto p:evs){
			if(p.se>=n){
				assert(r==-1);
				r=p.se%n;
			}
		}
		vec(pii) nevs;
		for(auto p:evs){
			if(p.fi<=r) continue;
			nevs.pb(p);
		}
		evs=nevs;
	}
	auto af=[&](int l,int r){
		// print(l,r);
		int now=0;
		set<int> st;
		rng(i,l,r+1){
			for(auto v:rbts[i%n]){
				st.insert(v);
			}
			assert(sz(st));
			auto it=st.lower_bound(b[i%n]);
			if(it==st.end()){
				st.erase(st.begin());
			}else{
				now+=1;
				// print(*it,b[i]);
				st.erase(it);
			}
		}
		return now;
	};
	int res=0;
	for(auto p:evs){
		res+=af(p.fi,p.se);
	}
	print(res);
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	958 ms	34860 KB	Output is correct
2	Correct	414 ms	33916 KB	Output is correct
3	Correct	584 ms	42292 KB	Output is correct
4	Correct	539 ms	43288 KB	Output is correct
5	Correct	377 ms	28144 KB	Output is correct
6	Correct	310 ms	27932 KB	Output is correct
7	Correct	393 ms	32160 KB	Output is correct
8	Correct	270 ms	29732 KB	Output is correct
9	Correct	342 ms	33848 KB	Output is correct
10	Correct	308 ms	30292 KB	Output is correct