답안 #623422

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
623422 2022-08-05T14:50:51 Z inksamurai Kralj (COCI16_kralj) C++17
140 / 140
958 ms 43288 KB
#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);
}
# 결과 실행 시간 메모리 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