oj.uz

Submission #773254

# Submission time Handle Problem Language Result Execution time Memory
773254 2023-07-04T17:45:22 Z therealpain Wall (IOI14_wall) C++17
100 / 100
 773 ms 138464 KB 
#include <bits/stdc++.h> 
#define fi first 
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK ""
 
using namespace std;
 
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
 
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 2e6 + 7;

int ans[N];
int n, k;

struct IntervalTree {
	int n;
	int st[4 * N];
	pair <int, int> lazy[4 * N];

	IntervalTree(int n) {
		this -> n = n;
		for (int i = 1; i <= 4 * n; ++i) {
			st[i] = 0;
			lazy[i] = mp(-1e9, 1e9);
		}
	}

	void fix(int id, int l, int r, int type) {
		if (type == 1) 
            maxi(st[id], lazy[id].fi);
		else 
            mini(st[id], lazy[id].se);
        if (l < r) {
            if (type == 1) {
                maxi(lazy[id << 1].fi, lazy[id].fi);
                maxi(lazy[id << 1].se, lazy[id].fi);
                maxi(lazy[id << 1 | 1].fi, lazy[id].fi);
                maxi(lazy[id << 1 | 1].se, lazy[id].fi);
            } else {
                mini(lazy[id << 1].fi, lazy[id].se);
                mini(lazy[id << 1].se, lazy[id].se);
                mini(lazy[id << 1 | 1].fi, lazy[id].se);
                mini(lazy[id << 1 | 1].se, lazy[id].se);
            }
        }
        if (type == 1) {
        	lazy[id].fi = -1e9;
        } else 
        	lazy[id].se = 1e9;
	}

	void update(int u, int v, int h, int type, int id = 1, int l = 1, int r = -1) {
		if (r < 0) r = n;
		fix(id, l, r, 0);
		fix(id, l, r, 1);
		if (l > v || r < u) return;
		if (u <= l && r <= v) {
			if (type == 1) {
				maxi(lazy[id].fi, h);
				maxi(lazy[id].se, h);
			} else {
				mini(lazy[id].fi, h);
				mini(lazy[id].se, h);
			}
			fix(id, l, r, type);
			return;
		}

		int mid = l + r >> 1;
		update(u, v, h, type, id << 1, l, mid);
		update(u, v, h, type, id << 1 | 1, mid + 1, r);
	}

	void get(int id = 1, int l = 1, int r = -1) {
		if (r < 0) r = n;
		fix(id, l, r, 0);
		fix(id, l, r, 1);
		if (l == r) {
			ans[l] = st[id];
			return;
		}

		int mid = l + r >> 1;
		get(id << 1, l, mid);
		get(id << 1 | 1, mid + 1, r);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	IntervalTree IT(n);
	for (int i = 0; i < k; ++i) {
		IT.update(left[i] + 1, right[i] + 1, height[i], op[i]);
	}
	IT.get();
	for (int i = 1; i <= n; ++i) {
		finalHeight[i - 1] = ans[i];
	}
}

Compilation message

wall.cpp: In member function 'void IntervalTree::update(int, int, int, int, int, int, int)':
wall.cpp:79:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |   int mid = l + r >> 1;
      |             ~~^~~
wall.cpp: In member function 'void IntervalTree::get(int, int, int)':
wall.cpp:93:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 94096 KB Output is correct
2 Correct 35 ms 94284 KB Output is correct
3 Correct 36 ms 94204 KB Output is correct
4 Correct 41 ms 94416 KB Output is correct
5 Correct 47 ms 94516 KB Output is correct
6 Correct 39 ms 94468 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 94212 KB Output is correct
2 Correct 135 ms 107840 KB Output is correct
3 Correct 226 ms 101452 KB Output is correct
4 Correct 583 ms 112568 KB Output is correct
5 Correct 313 ms 113632 KB Output is correct
6 Correct 305 ms 112056 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 94184 KB Output is correct
2 Correct 34 ms 94296 KB Output is correct
3 Correct 35 ms 94276 KB Output is correct
4 Correct 39 ms 94412 KB Output is correct
5 Correct 38 ms 94412 KB Output is correct
6 Correct 38 ms 94432 KB Output is correct
7 Correct 34 ms 94164 KB Output is correct
8 Correct 142 ms 107776 KB Output is correct
9 Correct 227 ms 101332 KB Output is correct
10 Correct 594 ms 112568 KB Output is correct
11 Correct 311 ms 113632 KB Output is correct
12 Correct 317 ms 112068 KB Output is correct
13 Correct 35 ms 94220 KB Output is correct
14 Correct 143 ms 107792 KB Output is correct
15 Correct 77 ms 95420 KB Output is correct
16 Correct 704 ms 112824 KB Output is correct
17 Correct 363 ms 112248 KB Output is correct
18 Correct 316 ms 112300 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 94172 KB Output is correct
2 Correct 37 ms 94308 KB Output is correct
3 Correct 37 ms 94268 KB Output is correct
4 Correct 41 ms 94440 KB Output is correct
5 Correct 42 ms 94588 KB Output is correct
6 Correct 40 ms 94412 KB Output is correct
7 Correct 36 ms 94216 KB Output is correct
8 Correct 136 ms 107860 KB Output is correct
9 Correct 225 ms 101432 KB Output is correct
10 Correct 592 ms 112756 KB Output is correct
11 Correct 316 ms 113632 KB Output is correct
12 Correct 310 ms 112144 KB Output is correct
13 Correct 35 ms 94140 KB Output is correct
14 Correct 142 ms 107876 KB Output is correct
15 Correct 75 ms 95488 KB Output is correct
16 Correct 706 ms 112868 KB Output is correct
17 Correct 318 ms 112244 KB Output is correct
18 Correct 315 ms 112244 KB Output is correct
19 Correct 764 ms 138340 KB Output is correct
20 Correct 714 ms 135848 KB Output is correct
21 Correct 729 ms 138464 KB Output is correct
22 Correct 721 ms 135896 KB Output is correct
23 Correct 713 ms 135860 KB Output is correct
24 Correct 746 ms 135908 KB Output is correct
25 Correct 710 ms 135864 KB Output is correct
26 Correct 773 ms 138440 KB Output is correct
27 Correct 728 ms 138440 KB Output is correct
28 Correct 712 ms 135952 KB Output is correct
29 Correct 724 ms 135944 KB Output is correct
30 Correct 715 ms 135928 KB Output is correct