oj.uz

Submission #1014175

# Submission time Handle Problem Language Result Execution time Memory
1014175 2024-07-04T13:35:10 Z AmirAli_H1 Wall (IOI14_wall) C++17
100 / 100
 726 ms 102416 KB 
// In the name of Allah

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo = 1e18 + 4;
const int maxn = (1 << 21) + 4;

int n, q;
pll t[2 * maxn];

void upd_lazy(int v, pll x) {
	if (max(t[v].F, x.F) <= min(t[v].S, x.S)) {
		t[v].F = max(t[v].F, x.F); t[v].S = min(t[v].S, x.S);
	}
	else {
		if (t[v].S < x.F) t[v] = Mp(x.F, x.F);
		else t[v] = Mp(x.S, x.S);
	}
}

void shift(int v) {
	pll x = t[v]; t[v] = Mp(-oo, oo);
	if (x == Mp(-oo, oo)) return ;
	for (int u : {2 * v + 1, 2 * v + 2}) {
		upd_lazy(u, x);
	}
}

void build(int v, int tl, int tr) {
	t[v] = Mp(-oo, oo);
	if (tr - tl == 1) return ;
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
}

void upd_val(int v, int tl, int tr, int l, int r, pll x) {
	l = max(l, tl); r = min(r, tr);
	if (l >= tr || r <= tl) return ;
	if (l == tl && r == tr) {
		upd_lazy(v, x);
		return ;
	}
	shift(v);
	int mid = (tl + tr) / 2;
	upd_val(2 * v + 1, tl, mid, l, r, x); upd_val(2 * v + 2, mid, tr, l, r, x);
}

ll get_val(int v, int tl, int tr, int i) {
	if (tr - tl == 1) {
		ll x = 0;
		x = max(x, t[v].F); x = min(x, t[v].S);
		return x;
	}
	shift(v);
	int mid = (tl + tr) / 2;
	if (i < mid) return get_val(2 * v + 1, tl, mid, i);
	else return get_val(2 * v + 2, mid, tr, i);
}

void buildWall(int Nx, int Qx, int op[], int lq[], int rq[], int hq[], int ans[]) {
	n = Nx; q = Qx;
	build(0, 0, n);
	for (int i = 0; i < q; i++) {
		rq[i]++;
		if (op[i] == 1) {
			upd_val(0, 0, n, lq[i], rq[i], Mp(hq[i], oo));
		}
		else {
			upd_val(0, 0, n, lq[i], rq[i], Mp(-oo, hq[i]));
		}
	}
	for (int i = 0; i < n; i++) ans[i] = get_val(0, 0, n, i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1164 KB Output is correct
6 Correct 4 ms 1368 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 91 ms 13904 KB Output is correct
3 Correct 122 ms 8528 KB Output is correct
4 Correct 433 ms 22416 KB Output is correct
5 Correct 221 ms 23440 KB Output is correct
6 Correct 196 ms 22060 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 352 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 9 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 125 ms 13916 KB Output is correct
9 Correct 160 ms 8612 KB Output is correct
10 Correct 439 ms 22516 KB Output is correct
11 Correct 190 ms 23524 KB Output is correct
12 Correct 209 ms 21840 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 88 ms 14000 KB Output is correct
15 Correct 25 ms 2424 KB Output is correct
16 Correct 497 ms 22756 KB Output is correct
17 Correct 199 ms 22100 KB Output is correct
18 Correct 205 ms 22100 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 2 ms 580 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 82 ms 13904 KB Output is correct
9 Correct 127 ms 8532 KB Output is correct
10 Correct 468 ms 22504 KB Output is correct
11 Correct 228 ms 23380 KB Output is correct
12 Correct 242 ms 21988 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 127 ms 13904 KB Output is correct
15 Correct 27 ms 2640 KB Output is correct
16 Correct 489 ms 22752 KB Output is correct
17 Correct 199 ms 22100 KB Output is correct
18 Correct 193 ms 22100 KB Output is correct
19 Correct 642 ms 102412 KB Output is correct
20 Correct 568 ms 99972 KB Output is correct
21 Correct 624 ms 102360 KB Output is correct
22 Correct 659 ms 99928 KB Output is correct
23 Correct 598 ms 99920 KB Output is correct
24 Correct 607 ms 99924 KB Output is correct
25 Correct 615 ms 99784 KB Output is correct
26 Correct 726 ms 102416 KB Output is correct
27 Correct 649 ms 102408 KB Output is correct
28 Correct 570 ms 99920 KB Output is correct
29 Correct 639 ms 99816 KB Output is correct
30 Correct 603 ms 99924 KB Output is correct