Submission #135213

#	Time	Username	Problem	Language	Result	Execution time	Memory
135213		arthurconmy	Wall (IOI14_wall)	C++14	24 / 100	424 ms	37212 KiB

wall

#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
	#include "wall.h"
#endif
using namespace std;
using pii=pair<int,int>;

#define ff first
#define ss second
#define pb push_back

const int MAXN = 100000;
int max_add[MAXN];
int min_rem[MAXN];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int i=0; i<MAXN; i++) min_rem[i] = int(1e9);

	priority_queue<pair<pii,int>> adders;
	priority_queue<pair<pii,int>> miners;

	for(int i=0; i<k; i++)
	{
		if(op[i]==1)
		{
			adders.push({{-left[i],right[i]},height[i]}); // NEGATIVE!!!
		}

		else
		{
			miners.push({{-left[i],right[i]},height[i]});
		}
	}

	priority_queue<pair<int,pii>> active; // first index is the answer and second is the [L,R]

	for(int i=0; i<n; i++)
	{
		while(!adders.empty() && adders.top().ff.ff == -i)
		{
			pair<pii,int> cur = adders.top();
			adders.pop();

			// cout << "ADDED " << -cur.ff.ff << " " << cur.ff.ss << endl;

			active.push({cur.ss,{-cur.ff.ff,cur.ff.ss}}); // UNDONE NEGATIVE
		}

		while(!active.empty() && active.top().ss.ss < i)
		{
			// cout << "REMOVED " << active.top().ss.ff << " " << active.top().ss.ss << endl;
			active.pop();
		}

		if(active.empty()) continue; // max_add[i]=0;

		max_add[i]=active.top().ff;
	}

	while(!active.empty()) active.pop();

	for(int i=0; i<n; i++)
	{
		while(!miners.empty() && miners.top().ff.ff == -i)
		{
			pair<pii,int> cur = miners.top();
			miners.pop();

			active.push({-cur.ss,{-cur.ff.ff,cur.ff.ss}});
		}

		while(!active.empty() && active.top().ss.ss < i)
		{
			active.pop();
		}

		if(active.empty()) continue;

		min_rem[i] = -active.top().ff;
	}

	for(int i=0; i<n; i++)
	{
		finalHeight[i] = min(max_add[i],min_rem[i]);
	}
}

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