oj.uz

Submission #878853

# Submission time Handle Problem Language Result Execution time Memory
878853 2023-11-25T10:44:25 Z Gray Wall (IOI14_wall) C++17
100 / 100
 533 ms 92448 KB 
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#include <cassert>
#define ll long long
#define ln "\n"
#define ff first
#define ss second
#define ld long double
const ll INF = 2e18;
const ll MOD = 1e9+7;
using namespace std;

struct SegTree{
	struct node{
		ll mn, mx;
	};
	node def = {INF, 0};
	vector<node> t;
	ll sz, rsz;
	SegTree(ll N){
		sz=1; while (sz<N) sz*=2;
		sz*=2; rsz=N;
		t.resize(sz, def);
	}
	
	void preprocess(ll v, ll chv1, ll chv2){
		if (t[v].mn != def.mn or t[v].mx!=def.mx){
			assert(t[v].mn>=t[v].mx);
			if (t[chv1].mx<t[v].mx){
				t[chv1].mx = t[v].mx;
				t[chv1].mn = min(t[chv1].mn, t[v].mn);
				if (t[chv1].mx>t[chv1].mn) t[chv1].mn = t[chv1].mx;
			}else if (t[chv1].mn>t[v].mn){
				t[chv1].mn = t[v].mn;
				t[chv1].mx = max(t[chv1].mx, t[v].mx);
				if (t[chv1].mx>t[chv1].mn) t[chv1].mx = t[chv1].mn;
			}else{

			}

			if (t[chv2].mx<t[v].mx){
				t[chv2].mx = t[v].mx;
				t[chv2].mn = min(t[chv2].mn, t[v].mn);
				if (t[chv2].mx>t[chv2].mn) t[chv2].mn = t[chv2].mx;
			}else if (t[chv2].mn>t[v].mn){
				t[chv2].mn = t[v].mn;
				t[chv2].mx = max(t[chv2].mx, t[v].mx);
				if (t[chv2].mx>t[chv2].mn) t[chv2].mx = t[chv2].mn;
			}else{

			}
		}
		t[v] = def;
	}
	void update_range(ll tl, ll tr, ll v, ll l, ll r, pair<ll, ll> &act){
		// cout << tl << " " << tr << " : " << l << " " << r << endl;
		if (tl!=tr) preprocess(v, v*2, v*2+1);
		if (tl==l and tr==r){
			if (act.ff==1){
				t[v].mx = max(t[v].mx, act.ss);
				t[v].mn = max(t[v].mn, t[v].mx);
			}else{
				t[v].mn = min(t[v].mn, act.ss);
				t[v].mx = min(t[v].mn, t[v].mx);
			}
			return;
		}
		if (l>r) return;
		ll tm = (tl+tr)/2;
		update_range(tl, tm, v*2, l, min(r, tm), act);
		update_range(tm+1, tr, v*2+1, max(l, tm+1), r, act);
	}
	void assemble(ll tl, ll tr, ll v, int ans[]){
		if (tl==tr){
			ans[tl] = (int)t[v].mx;
			return;
		}
		preprocess(v, v*2, v*2+1);
		ll tm = (tl+tr)/2;
		assemble(tl, tm, v*2, ans);
		assemble(tm+1, tr, v*2+1, ans);
	}
	void assemble(int ans[]){
		assemble(0, rsz-1, 1, ans);
	}
	void update(ll l, ll r, pair<ll, ll> act){
		update_range(0, rsz-1, 1, l, r, act);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree tr(n);
	for (ll i=0; i<k; i++){
		// cout << op[i] << endl;
		tr.update(left[i], right[i], {op[i], height[i]});	
		// tr.assemble(finalHeight);
		// for (ll j=0; j<n; j++) cout << finalHeight[j] << ' ';
		// cout << ln;
	}
	tr.assemble(finalHeight);
}

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 348 KB Output is correct
3 Correct 2 ms 360 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 952 KB Output is correct
6 Correct 4 ms 1112 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 8020 KB Output is correct
3 Correct 193 ms 4720 KB Output is correct
4 Correct 496 ms 22328 KB Output is correct
5 Correct 233 ms 22864 KB Output is correct
6 Correct 212 ms 21328 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 2 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 4 ms 1144 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 103 ms 13896 KB Output is correct
9 Correct 181 ms 8536 KB Output is correct
10 Correct 521 ms 22352 KB Output is correct
11 Correct 225 ms 22780 KB Output is correct
12 Correct 212 ms 21168 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 104 ms 14032 KB Output is correct
15 Correct 33 ms 2524 KB Output is correct
16 Correct 533 ms 22356 KB Output is correct
17 Correct 221 ms 21588 KB Output is correct
18 Correct 217 ms 21588 KB Output is correct

Subtask #4
39.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 348 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1368 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 102 ms 13852 KB Output is correct
9 Correct 178 ms 8540 KB Output is correct
10 Correct 507 ms 22424 KB Output is correct
11 Correct 221 ms 22692 KB Output is correct
12 Correct 226 ms 21328 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 105 ms 14004 KB Output is correct
15 Correct 30 ms 2396 KB Output is correct
16 Correct 528 ms 22184 KB Output is correct
17 Correct 220 ms 21652 KB Output is correct
18 Correct 221 ms 21848 KB Output is correct
19 Correct 512 ms 92028 KB Output is correct
20 Correct 508 ms 91988 KB Output is correct
21 Correct 512 ms 92088 KB Output is correct
22 Correct 505 ms 92104 KB Output is correct
23 Correct 513 ms 92044 KB Output is correct
24 Correct 507 ms 91988 KB Output is correct
25 Correct 513 ms 92244 KB Output is correct
26 Correct 532 ms 92448 KB Output is correct
27 Correct 520 ms 92264 KB Output is correct
28 Correct 515 ms 92244 KB Output is correct
29 Correct 514 ms 92244 KB Output is correct
30 Correct 519 ms 92244 KB Output is correct