Submission #128662

#	Time	Username	Problem	Language	Result	Execution time	Memory
128662		antimirage	Wall (IOI14_wall)	C++14	0 / 100	3034 ms	4984 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 1e5 + 5;

vector <int> add[N], del[N];

multiset <int> st;

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int a[]) {
	
	bool fl = 0;
	
	for (int i = 0; i < k; i++) {
		if (op[i] == 1) {
			add[l[i]].pb(h[i]);
			del[r[i] + 1].pb(h[i]);
		}
		else {
			if (fl == 0) {
				fl = 1;
				for (int i = 1; i <= n; i++) {
					for (auto it : add[i])
						st.insert(it);
					for (auto it : del[i])
						st.erase(st.lower_bound(it));
					
					if (!st.empty())
						a[i] = max(a[i], *(--st.end()) );
				}
				st.clear();
			}
			add[l[i]].pb(h[i]);
			del[r[i] + 1].pb(h[i]);
		}
	}
	if (fl == 0) {
		for (int i = 1; i <= n; i++) {
			for (auto it : add[i])
				st.insert(it);
			for (auto it : del[i])
				st.erase(st.lower_bound(it));
			
			if (!st.empty())
				a[i] = max(a[i], *(--st.end()) );
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			for (auto it : add[i])
				st.insert(it);
			for (auto it : del[i])
				st.erase(st.lower_bound(it));
			
			if (!st.empty())
				a[i] = min(a[i], *(st.begin()) );
		}
	}
}
/**
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
**/

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