oj.uz

Submission #329050

# Submission time Handle Problem Language Result Execution time Memory
329050 2020-11-18T20:09:36 Z super_j6 Wall (IOI14_wall) C++14
100 / 100
 964 ms 224872 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int inf = 0x3f3f3f3f;

struct segTree{
	int l, r;
	segTree *tl, *tr;
	int mn = 0, mx = inf;
	
	segTree(int a, int b){
		l = a, r = b;
		mn = 0, mx = inf;
		if(l != r){
			int mid = (l + r) / 2;
			tl = new segTree(l, mid);
			tr = new segTree(mid + 1, r);
		}
	}
	
	void upd(int vl, int vr){
		mn = min(max(mn, vl), vr);
		mx = min(max(mx, vl), vr);
	}
	
	void psh(){
		tl->upd(mn, mx), tr->upd(mn, mx);
		mn = 0, mx = inf;
	}
	
	void add(int a, int b, int vl, int vr){
		if(b < l || r < a) return;
		if(a <= l && r <= b) return upd(vl, vr);
		psh();
		tl->add(a, b, vl, vr), tr->add(a, b, vl, vr);
	}
	
	void sol(int ans[]){
		if(l == r) return (void)(ans[l] = mn);
		psh();
		tl->sol(ans), tr->sol(ans);
	}
};

void buildWall(int n, int q, int t[], int l[], int r[], int h[], int ans[]){
	segTree tre(0, n - 1);
	
	for(int i = 0; i < q; i++){
		if(t[i] & 1) tre.add(l[i], r[i], h[i], inf);
		else tre.add(l[i], r[i], 0, h[i]);
	}
	
	tre.sol(ans);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 1516 KB Output is correct
5 Correct 6 ms 1516 KB Output is correct
6 Correct 6 ms 1516 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 167 ms 13932 KB Output is correct
3 Correct 199 ms 9196 KB Output is correct
4 Correct 645 ms 27756 KB Output is correct
5 Correct 316 ms 28780 KB Output is correct
6 Correct 320 ms 27244 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 1516 KB Output is correct
5 Correct 6 ms 1516 KB Output is correct
6 Correct 7 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 167 ms 14060 KB Output is correct
9 Correct 181 ms 9196 KB Output is correct
10 Correct 661 ms 27756 KB Output is correct
11 Correct 333 ms 28908 KB Output is correct
12 Correct 331 ms 27244 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 163 ms 14060 KB Output is correct
15 Correct 31 ms 3308 KB Output is correct
16 Correct 658 ms 28012 KB Output is correct
17 Correct 317 ms 27644 KB Output is correct
18 Correct 316 ms 27500 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 1516 KB Output is correct
5 Correct 6 ms 1516 KB Output is correct
6 Correct 6 ms 1516 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 158 ms 13932 KB Output is correct
9 Correct 179 ms 9196 KB Output is correct
10 Correct 651 ms 27756 KB Output is correct
11 Correct 317 ms 28908 KB Output is correct
12 Correct 328 ms 27372 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 162 ms 13932 KB Output is correct
15 Correct 38 ms 3180 KB Output is correct
16 Correct 666 ms 28012 KB Output is correct
17 Correct 315 ms 27500 KB Output is correct
18 Correct 319 ms 27556 KB Output is correct
19 Correct 956 ms 224872 KB Output is correct
20 Correct 933 ms 222188 KB Output is correct
21 Correct 950 ms 224748 KB Output is correct
22 Correct 938 ms 222316 KB Output is correct
23 Correct 941 ms 222140 KB Output is correct
24 Correct 939 ms 222188 KB Output is correct
25 Correct 950 ms 222256 KB Output is correct
26 Correct 947 ms 224664 KB Output is correct
27 Correct 955 ms 224828 KB Output is correct
28 Correct 964 ms 222104 KB Output is correct
29 Correct 948 ms 222188 KB Output is correct
30 Correct 957 ms 222188 KB Output is correct