oj.uz

Submission #492633

# Submission time Handle Problem Language Result Execution time Memory
492633 2021-12-08T08:08:43 Z 8e7 Wall (IOI14_wall) C++17
100 / 100
 917 ms 84420 KB 
//Challenge: Accepted
#include "wall.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <assert.h>
#include <cmath>
#include <iomanip>
#include <random>
#include <unordered_set>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 2000005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 8e7;
struct segtree{
	int mi[4*maxn], ma[4*maxn], fi[4*maxn], a[maxn];	
	void init(int cur, int l, int r) {
		if (r <= l) return;
		mi[cur] = inf, ma[cur] = 0;
		if (r - l == 1) return;
		int m = (l + r) / 2;
		init(cur*2, l, m), init(cur*2+1, m, r);
	}
	void add(int ind, int type, int val) {
		if (type == 0 && val < mi[ind]) mi[ind] = val, fi[ind] = 1;
		if (type == 1 && val > ma[ind]) ma[ind] = val, fi[ind] = 0;
		if (fi[ind]) ma[ind] = min(ma[ind], mi[ind]);
		else mi[ind] = max(mi[ind], ma[ind]);
	}
	void push(int cur, int l, int r) {
		if (r - l > 1) {
			if (!fi[cur]) {
				add(cur*2, 0, mi[cur]), add(cur*2, 1, ma[cur]);
				add(cur*2+1, 0, mi[cur]), add(cur*2+1, 1, ma[cur]);
			} else {
				add(cur*2, 1, ma[cur]), add(cur*2, 0, mi[cur]);
				add(cur*2+1, 1, ma[cur]), add(cur*2+1, 0, mi[cur]);
			}
		} else {
			if (fi[cur]) a[l] = min(max(a[l], ma[cur]), mi[cur]);
			else a[l] = max(min(a[l], mi[cur]), ma[cur]);
		}
		ma[cur] = 0, mi[cur] = inf, fi[cur] = 0;
	}
	void modify(int cur, int l, int r, int ql, int qr, int val, int type) {
		if (r <= l || qr <= l || ql >= r) return;
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			if (type) ma[cur] = val;
			else mi[cur] = val;		
			return;
		}
		int m = (l + r) / 2;
		modify(cur*2, l, m, ql, qr, val, type);
		modify(cur*2+1, m, r, ql, qr, val, type);
	}
	void build(int cur, int l, int r) {
		if (r <= l) return;
		push(cur, l, r);
		if (r - l == 1) return;
		int m = (l + r) / 2;
		build(cur*2, l, m), build(cur*2+1, m, r);	
	}
} seg;
void buildWall(int n, int k, int op[], int lef[], int rig[], int h[], int ret[]) {
	seg.init(1, 0, n);
	for (int i = 0;i < k;i++) {
		seg.modify(1, 0, n, lef[i], rig[i]+1, h[i], 2 - op[i]);	
	}
	seg.build(1, 0, n);
	for (int i = 0;i < n;i++) ret[i] = seg.a[i];
}
/*
5 5
1 0 4 5
2 2 3 2
1 1 2 4
2 2 4 1
1 1 3 3

4 6
1 3 3 1
1 1 2 2
1 0 0 4
2 0 1 2
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 928 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 5 ms 972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 120 ms 8116 KB Output is correct
3 Correct 214 ms 4480 KB Output is correct
4 Correct 699 ms 12232 KB Output is correct
5 Correct 256 ms 12740 KB Output is correct
6 Correct 246 ms 12700 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 10 ms 1016 KB Output is correct
5 Correct 5 ms 944 KB Output is correct
6 Correct 5 ms 992 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 129 ms 9072 KB Output is correct
9 Correct 198 ms 5320 KB Output is correct
10 Correct 708 ms 13032 KB Output is correct
11 Correct 264 ms 13624 KB Output is correct
12 Correct 256 ms 13556 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 125 ms 9044 KB Output is correct
15 Correct 47 ms 2244 KB Output is correct
16 Correct 891 ms 13376 KB Output is correct
17 Correct 294 ms 13332 KB Output is correct
18 Correct 268 ms 13292 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 10 ms 972 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 5 ms 972 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 124 ms 9004 KB Output is correct
9 Correct 211 ms 5428 KB Output is correct
10 Correct 730 ms 13060 KB Output is correct
11 Correct 251 ms 13640 KB Output is correct
12 Correct 254 ms 13544 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 122 ms 8960 KB Output is correct
15 Correct 50 ms 2344 KB Output is correct
16 Correct 917 ms 13396 KB Output is correct
17 Correct 277 ms 13400 KB Output is correct
18 Correct 279 ms 13404 KB Output is correct
19 Correct 743 ms 84420 KB Output is correct
20 Correct 748 ms 81764 KB Output is correct
21 Correct 735 ms 84104 KB Output is correct
22 Correct 736 ms 81624 KB Output is correct
23 Correct 731 ms 81612 KB Output is correct
24 Correct 739 ms 81636 KB Output is correct
25 Correct 721 ms 81604 KB Output is correct
26 Correct 711 ms 84124 KB Output is correct
27 Correct 732 ms 83900 KB Output is correct
28 Correct 708 ms 81556 KB Output is correct
29 Correct 720 ms 81456 KB Output is correct
30 Correct 716 ms 81544 KB Output is correct