Submission #547645

#	Time	Username	Problem	Language	Result	Execution time	Memory
547645		amunduzbaev	Exercise Deadlines (CCO20_day1problem2)	C++17	25 / 25	89 ms	14212 KiB

Main

#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const int N = 2e5 + 5;
struct ST{
	int tree[N];
	void add(int i, int v){ i++;
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){ i++;
		int r=0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
}tree;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<int> a(n);
	vector<vector<int>> to(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
		to[--a[i]].push_back(i);
	}
	
	priority_queue<int> q;
	long long res = 0;
	for(int i=n-1;~i;i--){
		for(auto x : to[i]) q.push(x);
		if(q.empty()){
			cout<<-1<<"\n";
			return 0;
		}
		
		int p = q.top(); q.pop();
		int j = p + tree.get(p);
		res += (i - j);
		tree.add(p, -1);
	}
	
	cout<<res<<"\n";
}

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