제출 #219186

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219186		oolimry	별자리 3 (JOI20_constellation3)	C++14	0 / 100	8 ms	6656 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

typedef pair<long long, long long> ii;
long long H[200005];
priority_queue<ii, vector<ii>, greater<ii> > pq[200005]; ///offset applied
long long offset[200005];
long long anything[200005]; ///no offset applied
int p[200005];

int findSet(int u){
	if(u == p[u])return p[u];
	else{
		p[u] = findSet(p[u]);
		return p[u];
	}
}

void unionSet(int u, int v){
	u = findSet(u); v = findSet(v);

	/*
	if(pq[u].size() > pq[v].size()){
		swap(pq[u],pq[v]);
		swap(offset[u],offset[v]);
		swap(anything[u],anything[v]);
	}
	*/
	
	offset[v] += anything[u];
	///push the things from pq[u] to pq[v];
	while(!pq[u].empty()){
		ii x = pq[u].top();
		pq[u].pop();
		
		x.second += offset[u];
		x.second += anything[v];
		x.second -= offset[v];
		pq[v].push(x);
	}
	
	p[u] = v;
	anything[v] = max(anything[v], anything[u]);
}

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin >> n;
	int order[n];
	
	long long total = 0;
	for(int i = 0;i < n;i++){
		cin >> H[i];
		order[i] = i;
	}
	int m; cin >> m;
	for(int i = 0;i < m;i++){
		int x, y, c; cin >> x >> y >> c;
		x--;
		pq[x].push(ii(y,c));
		total += (long long) c;
	}
	
	for(int i = 0;i < n;i++) p[i] = i;
	
	sort(order, order + n, [&](int a, int b){ return H[a] < H[b]; });
	
	for(int i : order){
		
		/*
		cout << i << ":\n";
		
		for(int j = 0;j < n;j++) cout << findSet(j) << " "; cout << endl;
		for(int j = 0;j < n;j++) cout << anything[j] << " "; cout << endl;
		for(int j = 0;j < n;j++) cout << offset[j] << " "; cout << endl;
		for(int j = 0;j < n;j++){
			vector<ii> v;
			cout << j << ": ";
			while(!pq[j].empty()){
				v.push_back(pq[j].top());
				pq[j].pop();
			}
			
			for(ii x : v){
				cout << "(" << x.first << ", " << x.second + offset[j] << ") ";
				pq[j].push(x);
			}
			cout << "\n";
		}
		*/
		
		if(i != 0 && H[i-1] <= H[i]){
			int u = findSet(i-1); int v = findSet(i);
			if(u != v){
				while(!pq[u].empty()){
					ii x = pq[u].top();
					if(x.first > H[i]) break;
					
					pq[u].pop();
					anything[u] = max(anything[u], x.second + offset[u]);
					//if(i == 5) cout << anything[u] << "G\n";
				}
				unionSet(u,v);
			}
		}
		
		//cout << anything[i] << "A\n";
		
		if(i != n-1 && H[i+1] <= H[i]){
			int u = findSet(i+1); int v = findSet(i);
			if(u != v){
				while(!pq[u].empty()){
					ii x = pq[u].top();
					if(x.first > H[i]) break;
					
					pq[u].pop();
					anything[u] = max(anything[u], x.second + offset[u]);
					//if(i == 5) cout << anything[u] << "G\n";
				}
				unionSet(u,v);
			}
		}
	}
	
	/*
	cout << "end:\n";
		
	for(int j = 0;j < n;j++) cout << findSet(j) << " "; cout << endl;
	for(int j = 0;j < n;j++) cout << anything[j] << " "; cout << endl;
	for(int j = 0;j < n;j++) cout << offset[j] << " "; cout << endl;
	for(int j = 0;j < n;j++){
		cout << j << ": ";
		vector<ii> v;
		while(!pq[j].empty()){
			v.push_back(pq[j].top());
			pq[j].pop();
		}
		
		for(ii x : v){
			cout << "(" << x.first << ", " << x.second + offset[j] << ") ";
			pq[j].push(x);
		}
		cout << "\n";
	}
	*/
	
	int last = order[n-1];
	long long ans = anything[last];
	while(!pq[last].empty()){
		ans = max(ans, pq[last].top().second + offset[last]);
		pq[last].pop();
	}
	
	ans = max(ans, offset[last]);
	cout << total - ans;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 65