oj.uz

Submission #485445

# Submission time Handle Problem Language Result Execution time Memory
485445 2021-11-07T19:06:40 Z Eyed Wall (IOI14_wall) C++14
100 / 100
 979 ms 100548 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <climits>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll MOD = 1e9 + 7;

struct range {
	int l;
	int r;
	range(int xx = 0, int yy = 0) : l(xx), r(yy) {};
};

int nn, kk;
int tree[8000055];
range lazy[8000055];
bool mark[8000055];

void app(int i, int j) {
	lazy[i].l = max(lazy[i].l, lazy[j].l);
	lazy[i].r = max(lazy[i].r, lazy[j].l);
	lazy[i].l = min(lazy[i].l, lazy[j].r);
	lazy[i].r = min(lazy[i].r, lazy[j].r);
}

void push(int v) {
		app(2 * v, v);
		app(2 * v + 1, v);
		lazy[v].l = 0;
		lazy[v].r = 100005;
		mark[v] = false;

}

void update(int v, int tl, int tr, int ll, int rr, int op, int x) {
	if (ll > rr) return;
	if (ll <= tl && rr >= tr) {
		if (op == 0) {
			lazy[v].l = max(lazy[v].l, x);
			lazy[v].r = max(lazy[v].r, lazy[v].l);
		}
		if (op == 1) {
			lazy[v].r = min(lazy[v].r, x);
			lazy[v].l = min(lazy[v].l, lazy[v].r);
		}
		mark[v] = true;
		return;
	}
	push(v);
	int pos = (tl + tr) / 2;
	update(2 * v, tl, pos, ll, min(pos, rr), op, x);
	update(2 * v + 1, pos + 1, tr, max(pos + 1, ll), rr, op, x);
}

int get(int v, int tl, int tr, int x) {
	if (tl == tr) {
	//	cout << lazy[v].l << " " << lazy[v].r << "; ";
		return lazy[v].l;
	}
	push(v);
	int tm = (tl + tr) / 2;
	if (x <= tm) return get(2 * v, tl, tm, x);
	else return get(2 * v + 1, tm + 1, tr, x);
}
void update(int ll, int rr, int op, int x) { update(1, 0, nn+1, ll, rr, op, x); }
int get(int x) { return get(1, 0, nn+1, x); }

void buildWall(int n, int k, int op[], int left[], int right[],
	int height[], int finalHeight[]) {
	nn = n;
	kk = k;
	for (int i = 0; i < n; ++i) tree[i] = 0;
	for (int i = 0; i < 8000055; ++i) {
		lazy[i].l = 0;
		lazy[i].r = 100005;
	}
	for (int i = 0; i < k; ++i) update(left[i], right[i], op[i] - 1, height[i]);
	for (int i = 0; i < n; ++i) finalHeight[i] = get(i);
	return;
}
//
//int main(int argc, char* argv[]) {
//	/*const char* FIN  = "sample.in";
//	const char* FOUT = "sample.out";
//	const char* inFile = argc > 1 ? argv[1] : FIN;
//	ifstream cin(inFile);
//	ofstream cout(FOUT);*/
//
//	cin >> nn >> kk;
//	for (int i = 0; i < nn; ++i) cin >> tree[i];
//	for (int i = 0; i < 8000005; ++i) {
//		lazy[i].l = 0;
//		lazy[i].r = 100005;
//	}
//	for (int i = 0; i < kk; ++i) {
//		int o, ll, rr, x;
//		cin >> o >> ll >> rr >> x;
//		update(ll, rr, o, x);
//		for (int i = 0; i < nn; ++i) cout << get(i) << " ";
//		
//		cout << endl; 
//		//o == 0 means adding, o == 1 means removing
//	}
//	for (int i = 0; i < nn; ++i) cout << get(i) << endl;
//
//
//	return 0;
//}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62916 KB Output is correct
2 Correct 45 ms 62940 KB Output is correct
3 Correct 35 ms 62924 KB Output is correct
4 Correct 40 ms 63180 KB Output is correct
5 Correct 44 ms 63156 KB Output is correct
6 Correct 38 ms 63180 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 62920 KB Output is correct
2 Correct 181 ms 70932 KB Output is correct
3 Correct 198 ms 66644 KB Output is correct
4 Correct 445 ms 72168 KB Output is correct
5 Correct 314 ms 72772 KB Output is correct
6 Correct 304 ms 72704 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 62924 KB Output is correct
2 Correct 36 ms 63064 KB Output is correct
3 Correct 36 ms 62968 KB Output is correct
4 Correct 43 ms 63152 KB Output is correct
5 Correct 42 ms 63152 KB Output is correct
6 Correct 39 ms 63180 KB Output is correct
7 Correct 34 ms 62872 KB Output is correct
8 Correct 176 ms 70984 KB Output is correct
9 Correct 178 ms 66628 KB Output is correct
10 Correct 449 ms 72304 KB Output is correct
11 Correct 315 ms 72672 KB Output is correct
12 Correct 345 ms 72752 KB Output is correct
13 Correct 35 ms 62804 KB Output is correct
14 Correct 172 ms 70980 KB Output is correct
15 Correct 59 ms 63936 KB Output is correct
16 Correct 436 ms 72488 KB Output is correct
17 Correct 299 ms 72388 KB Output is correct
18 Correct 309 ms 72756 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 62924 KB Output is correct
2 Correct 36 ms 62968 KB Output is correct
3 Correct 36 ms 62992 KB Output is correct
4 Correct 39 ms 63172 KB Output is correct
5 Correct 40 ms 63208 KB Output is correct
6 Correct 39 ms 63180 KB Output is correct
7 Correct 35 ms 63044 KB Output is correct
8 Correct 173 ms 71012 KB Output is correct
9 Correct 178 ms 66628 KB Output is correct
10 Correct 448 ms 72188 KB Output is correct
11 Correct 308 ms 72724 KB Output is correct
12 Correct 319 ms 72712 KB Output is correct
13 Correct 34 ms 62788 KB Output is correct
14 Correct 178 ms 70976 KB Output is correct
15 Correct 61 ms 63940 KB Output is correct
16 Correct 442 ms 72516 KB Output is correct
17 Correct 302 ms 72516 KB Output is correct
18 Correct 311 ms 72496 KB Output is correct
19 Correct 958 ms 100376 KB Output is correct
20 Correct 947 ms 97860 KB Output is correct
21 Correct 954 ms 100348 KB Output is correct
22 Correct 954 ms 97948 KB Output is correct
23 Correct 979 ms 97864 KB Output is correct
24 Correct 952 ms 98000 KB Output is correct
25 Correct 942 ms 97884 KB Output is correct
26 Correct 949 ms 100548 KB Output is correct
27 Correct 951 ms 100380 KB Output is correct
28 Correct 947 ms 97940 KB Output is correct
29 Correct 956 ms 97932 KB Output is correct
30 Correct 951 ms 97840 KB Output is correct