oj.uz

Submission #135213

# Submission time Handle Problem Language Result Execution time Memory
135213 2019-07-23T20:15:12 Z arthurconmy Wall (IOI14_wall) C++14
24 / 100
 424 ms 37212 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Incorrect 5 ms 1016 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 417 ms 30968 KB Output is correct
3 Correct 190 ms 15676 KB Output is correct
4 Correct 411 ms 33628 KB Output is correct
5 Correct 424 ms 37212 KB Output is correct
6 Correct 408 ms 32700 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Incorrect 5 ms 1016 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Incorrect 5 ms 1012 KB Output isn't correct
3 Halted 0 ms 0 KB -