oj.uz

Submission #128662

# Submission time Handle Problem Language Result Execution time Memory
128662 2019-07-11T08:13:23 Z antimirage Wall (IOI14_wall) C++14
0 / 100
 3000 ms 4984 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3006 ms 4984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3013 ms 4984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3013 ms 4984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3034 ms 4984 KB Time limit exceeded
2 Halted 0 ms 0 KB -