oj.uz

Submission #132076

# Submission time Handle Problem Language Result Execution time Memory
132076 2019-07-18T09:31:31 Z Sorting Wall (IOI14_wall) C++14
100 / 100
 1572 ms 99480 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 7;
const int inf = 1e9;

struct node{
	int mn, mx;

	node(){
		mx = 0;
		mn  = inf;
	};
	node(int _mn, int _mx){
		mn = _mn;
		mx = _mx;
	}

	friend void unite(node &prev, node after){
		prev.mn = min(prev.mn, after.mn);
		prev.mx = max(prev.mx, after.mx);

		if(prev.mx > prev.mn){
			if(after.mx == prev.mx){
				prev.mn = prev.mx;
			}
			else{
				prev.mx = prev.mn;
			}
		}
	}
};

node st[4 * N];

void update(int idx, int l, int r, int sl, int sr, node val){
	if(l != r){
		unite(st[2 * idx], st[idx]);
		unite(st[2 * idx + 1], st[idx]);
		st[idx] = node();
	}

	if(l > sr || r < sl){
		return;
	}
	if(sl <= l && r <= sr){
		unite(st[idx], val);

		return;
	}

	int mid = (l + r) / 2;

	update(2 * idx, l, mid, sl, sr, val);
	update(2 * idx + 1, mid + 1, r, sl, sr, val);
}

int query(int idx, int l, int r, int s){
	if(l != r){
		unite(st[2 * idx], st[idx]);
		unite(st[2 * idx + 1], st[idx]);
		st[idx] = node();
	}

	if(l > s || r < s){
		return node().mx;
	}
	if(l == r && l == s){
		return st[idx].mx;
	}

	int mid = (l + r) >> 1;

	int lvalue = query(2 * idx, l, mid, s);
	int rvalue = query(2 * idx + 1, mid + 1, r, s);

	return max(lvalue, rvalue);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i = 0; i < k; i++){
		node t;

		if(op[i] == 1){
			t = node(inf, height[i]);
		}
		else{
			t = node(height[i], 0);
		}

		update(1, 0, n - 1, left[i], right[i], t);
	}

	for(int i = 0; i < n; i++){
		finalHeight[i] = query(1, 0, n - 1, i); 
	}
}

/*int n, k, op2[N], left2[N], right2[N], height2[N], finalHeight2[N];

int main(){
	cin >> n >> k;

	for(int i = 0; i < k; i++){
		cin >> op2[i] >> left2[i] >> right2[i] >> height2[i];
	}

	buildWall(n, k, op2, left2, right2, height2, finalHeight2);

	for(int i = 0; i < n; i++){
		cout << finalHeight2[i] << " ";
	}
	cout << "\n";
	
	return 0;
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 62968 KB Output is correct
2 Correct 56 ms 63096 KB Output is correct
3 Correct 57 ms 62968 KB Output is correct
4 Correct 67 ms 63068 KB Output is correct
5 Correct 62 ms 63236 KB Output is correct
6 Correct 62 ms 63224 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 62968 KB Output is correct
2 Correct 231 ms 70944 KB Output is correct
3 Correct 317 ms 66408 KB Output is correct
4 Correct 799 ms 71388 KB Output is correct
5 Correct 434 ms 82220 KB Output is correct
6 Correct 412 ms 80600 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 62972 KB Output is correct
2 Correct 66 ms 62968 KB Output is correct
3 Correct 56 ms 62968 KB Output is correct
4 Correct 69 ms 63252 KB Output is correct
5 Correct 62 ms 63224 KB Output is correct
6 Correct 62 ms 63180 KB Output is correct
7 Correct 55 ms 62968 KB Output is correct
8 Correct 232 ms 76552 KB Output is correct
9 Correct 307 ms 70136 KB Output is correct
10 Correct 788 ms 81032 KB Output is correct
11 Correct 464 ms 82008 KB Output is correct
12 Correct 430 ms 80636 KB Output is correct
13 Correct 64 ms 62972 KB Output is correct
14 Correct 246 ms 76636 KB Output is correct
15 Correct 107 ms 64384 KB Output is correct
16 Correct 1038 ms 81400 KB Output is correct
17 Correct 442 ms 80760 KB Output is correct
18 Correct 433 ms 80632 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 62972 KB Output is correct
2 Correct 56 ms 63004 KB Output is correct
3 Correct 58 ms 62968 KB Output is correct
4 Correct 65 ms 63096 KB Output is correct
5 Correct 69 ms 63284 KB Output is correct
6 Correct 62 ms 63224 KB Output is correct
7 Correct 55 ms 62968 KB Output is correct
8 Correct 230 ms 76636 KB Output is correct
9 Correct 311 ms 70152 KB Output is correct
10 Correct 818 ms 81016 KB Output is correct
11 Correct 434 ms 82108 KB Output is correct
12 Correct 426 ms 80504 KB Output is correct
13 Correct 55 ms 62936 KB Output is correct
14 Correct 235 ms 76552 KB Output is correct
15 Correct 118 ms 64120 KB Output is correct
16 Correct 1029 ms 81316 KB Output is correct
17 Correct 441 ms 80716 KB Output is correct
18 Correct 432 ms 80716 KB Output is correct
19 Correct 1563 ms 99420 KB Output is correct
20 Correct 1522 ms 96868 KB Output is correct
21 Correct 1546 ms 99480 KB Output is correct
22 Correct 1522 ms 97016 KB Output is correct
23 Correct 1521 ms 97084 KB Output is correct
24 Correct 1536 ms 96900 KB Output is correct
25 Correct 1541 ms 96952 KB Output is correct
26 Correct 1542 ms 99392 KB Output is correct
27 Correct 1572 ms 99452 KB Output is correct
28 Correct 1525 ms 96884 KB Output is correct
29 Correct 1524 ms 96884 KB Output is correct
30 Correct 1538 ms 96832 KB Output is correct