Submission #902395

#	Time	Username	Problem	Language	Result	Execution time	Memory
902395		pcc	Exercise Deadlines (CCO20_day1problem2)	C++14	25 / 25	423 ms	22712 KiB

Main

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define ordered_set(T) tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>

ordered_set(int) st,pos;
const int mxn = 2e5+10;
int arr[mxn];
std::priority_queue<pii,vector<pii>,less<pii>> pq;
int N;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<=N;i++)cin>>arr[i],pos.insert(i),pq.push(make_pair(arr[i],i));
	ll ans = 0;
	while(!pos.empty()){
		int now = pos.size();
		while(!pq.empty()&&pq.top().fs>=now){
			if(pos.find(pq.top().sc) != pos.end()){
				st.insert(pq.top().sc);
				pq.pop();
			}
		}
		/*
		cout<<now<<":"<<endl;
		for(auto &i:st)cout<<i<<' ';cout<<endl;
		for(auto &i:pos)cout<<i<<' ';cout<<endl;

	   */
		if(st.empty()){
			cout<<-1;
			return 0;
		}
		int tar = *st.rbegin();
		ans += now-pos.order_of_key(tar)-1;
		pos.erase(tar);
		st.erase(tar);
	}
	cout<<ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 8 / 8