제출 #1042050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042050		ALeonidou	벽 (IOI14_wall)	C++17	24 / 100	142 ms	30536 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define ll int
#define F first
#define S second
#define sz(x) (ll)x.size()
#define endl "\n"
#define pb push_back
#define inf 1000000000

typedef vector <ll> vi;
typedef pair <ll,ll> ii;
typedef vector <ii> vii;
typedef pair <ll, ii> iii;
typedef vector <iii> viii;

#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;

void printVct(vi &v){
    for (ll i =0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

void buildWall(ll n, ll k, ll op[], ll left[], ll right[], ll height[], ll finalHeight[]){

	// for (ll i =0; i<k; i++){
	// 	left[i]--;
	// 	right[i]--;
	// }

	vector <vii> q(n, vii());
	ll lastI = -1;
	for (ll i =0; i<k && op[i] == 1; i++){
		q[left[i]].pb(ii(height[i], right[i]));
		lastI = i;
	}

	priority_queue <ii, vii, less<ii> > pq1;
	ll curH = 0, curR = 0;
	for (ll i = 0; i<n; i++){
		// dbg3(i, curH, curR);
		if (i > curR){
			// dbg2(i,curR)
			curH = 0;
		}
		for (ll j =0; j<sz(q[i]); j++){
			pq1.push(q[i][j]);
		}
		
		while (!pq1.empty() && pq1.top().S < i) pq1.pop();
		if (!pq1.empty()){
			ii f = pq1.top();
			ll h = f.F;
			ll r = f.S;

			if (h > curH){
				// cout<<"IN"<<endl;
				pq1.pop();
				if (curH > 0){
					pq1.push(ii(curH, curR));
				}
				curH = h;
				curR = r;
			}
		}
		// dbg(curH);

		finalHeight[i] = curH;
		// cout<<endl;
	}

	// return;

	q.assign(n, vii());
	for (ll i =lastI+1; i<k; i++){
		q[left[i]].pb(ii(height[i], right[i]));
	}
	// for (ll i =0; i<n; i++){
	// 	for (ll j =0; j<sz(q[i]); j++){
	// 		cout<<"("<<q[i][j].F<<" "<<q[i][j].S<<") ";
	// 	}
	// 	cout<<endl;
	// }
	priority_queue <ii, vii, greater<ii> > pq2;
	curH = inf, curR = 0;
	for (ll i = 0; i<n; i++){
		// dbg3(i,curH, curR);
		if (i > curR){
			curH = inf;
		}
		for (ll j =0; j<sz(q[i]); j++){
			pq2.push(q[i][j]);
		}
		
		while (!pq2.empty() && pq2.top().S < i) pq2.pop();
		if (!pq2.empty()){
			ii f = pq2.top();
			ll h = f.F;
			ll r = f.S;
			
			if (h < curH){
				pq2.pop();
				if (curH < inf){
					pq2.push(ii(curH, curR));
				}
				curH = h;
				curR = r;
			}
		}

		finalHeight[i] = min(finalHeight[i], curH);
	}

	return;
}

• Subtask 1: 0 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39