oj.uz

Submission #897515

# Submission time Handle Problem Language Result Execution time Memory
897515 2024-01-03T10:38:01 Z oblantis Wall (IOI14_wall) C++17
61 / 100
 340 ms 26716 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 = 2e5 + 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 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 904 KB Output is correct
5 Correct 4 ms 2908 KB Output is correct
6 Correct 4 ms 3160 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 432 KB Output is correct
2 Correct 104 ms 13908 KB Output is correct
3 Correct 63 ms 10116 KB Output is correct
4 Correct 137 ms 24656 KB Output is correct
5 Correct 145 ms 25680 KB Output is correct
6 Correct 158 ms 22012 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 968 KB Output is correct
5 Correct 5 ms 2908 KB Output is correct
6 Correct 5 ms 3112 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 106 ms 14008 KB Output is correct
9 Correct 58 ms 10320 KB Output is correct
10 Correct 139 ms 24688 KB Output is correct
11 Correct 143 ms 25684 KB Output is correct
12 Correct 156 ms 22096 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 112 ms 14072 KB Output is correct
15 Correct 23 ms 4184 KB Output is correct
16 Correct 337 ms 24912 KB Output is correct
17 Correct 218 ms 24400 KB Output is correct
18 Correct 226 ms 24408 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 4 ms 2908 KB Output is correct
6 Correct 4 ms 2908 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 109 ms 13900 KB Output is correct
9 Correct 62 ms 10316 KB Output is correct
10 Correct 140 ms 24656 KB Output is correct
11 Correct 159 ms 25668 KB Output is correct
12 Correct 156 ms 22096 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 110 ms 13844 KB Output is correct
15 Correct 21 ms 4184 KB Output is correct
16 Correct 340 ms 24932 KB Output is correct
17 Correct 224 ms 24344 KB Output is correct
18 Correct 228 ms 24392 KB Output is correct
19 Runtime error 131 ms 26716 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -