oj.uz

Submission #897516

# Submission time Handle Problem Language Result Execution time Memory
897516 2024-01-03T10:38:44 Z oblantis Wall (IOI14_wall) C++17
100 / 100
 636 ms 104648 KB 
#include "wall.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
const ll inf = 1e18 + 10000;
const int mod = 1e9+7;
const int maxn = 2e6 + 12;

int mx[maxn * 4], mn[maxn * 4], c[maxn * 4], xl, xr, x, wt, nw;
void rlx(int v){
	c[v * 2 + 1] = c[v * 2 + 2] = mn[v * 2 + 1] = mn[v * 2 + 2] = mx[v * 2 + 1] = mx[v * 2 + 2] = c[v];
	c[v] = -1;
}
void upd(int v, int l, int r){
	if(xr < l || r < xl)return;
	if(wt == 1 && mn[v] >= x)return;
	if(wt == 2 && mx[v] <= x)return;
	if(xl <= l && r <= xr){
		if(wt == 1 && mx[v] <= x){
			mx[v] = mn[v] = x;
			c[v] = x;
			return;
		}
		if(wt == 2 && mn[v] >= x){
			mn[v] = mx[v] = x;
			c[v] = x;
			return;
		}
	}
	if(c[v] != -1){
		rlx(v);
	}
	upd(v * 2 + 1, l, (l + r) / 2), upd(v * 2 + 2, (l + r) / 2 + 1, r);
	mn[v] = min(mn[v * 2 + 1], mn[v * 2 + 2]), mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}
int get(int v, int l, int r){
	if(l == r){
		return mn[v];
	}
	if(c[v] != -1)rlx(v);
	if((l + r) / 2 < nw)return get(v * 2 + 2, (l + r) / 2 + 1, r);
	else return get(v * 2 + 1, l, (l + r) / 2); 
}
void buildWall(int n, int k, int op[], int left[], int right[], int h[], int fh[]){
	for(int i = 0; i < n * 4; i++)c[i] = -1;
	for(int i = 0; i < k; i++){
		wt = op[i], xl = left[i], xr = right[i], x = h[i];
		upd(0, 0, n);
	}
	for(int i = 0; i < n; i++){
		nw = i;
		fh[i] = get(0, 0, n);
	}
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 532 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 101 ms 8152 KB Output is correct
3 Correct 60 ms 6568 KB Output is correct
4 Correct 141 ms 13132 KB Output is correct
5 Correct 138 ms 13652 KB Output is correct
6 Correct 150 ms 13476 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 102 ms 8184 KB Output is correct
9 Correct 60 ms 6524 KB Output is correct
10 Correct 137 ms 13136 KB Output is correct
11 Correct 145 ms 13896 KB Output is correct
12 Correct 152 ms 13560 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 105 ms 8272 KB Output is correct
15 Correct 21 ms 3672 KB Output is correct
16 Correct 340 ms 13264 KB Output is correct
17 Correct 213 ms 13288 KB Output is correct
18 Correct 215 ms 13196 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 980 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 102 ms 8168 KB Output is correct
9 Correct 60 ms 6552 KB Output is correct
10 Correct 134 ms 13140 KB Output is correct
11 Correct 138 ms 13648 KB Output is correct
12 Correct 150 ms 13648 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 105 ms 8232 KB Output is correct
15 Correct 21 ms 3676 KB Output is correct
16 Correct 335 ms 13376 KB Output is correct
17 Correct 214 ms 13344 KB Output is correct
18 Correct 220 ms 13396 KB Output is correct
19 Correct 621 ms 93248 KB Output is correct
20 Correct 612 ms 101324 KB Output is correct
21 Correct 622 ms 101676 KB Output is correct
22 Correct 619 ms 101220 KB Output is correct
23 Correct 614 ms 98304 KB Output is correct
24 Correct 624 ms 102180 KB Output is correct
25 Correct 612 ms 102160 KB Output is correct
26 Correct 636 ms 104648 KB Output is correct
27 Correct 622 ms 104612 KB Output is correct
28 Correct 612 ms 98648 KB Output is correct
29 Correct 628 ms 102072 KB Output is correct
30 Correct 613 ms 102228 KB Output is correct