oj.uz

Submission #722614

# Submission time Handle Problem Language Result Execution time Memory
722614 2023-04-12T12:41:29 Z penguin133 Wall (IOI14_wall) C++17
100 / 100
 1754 ms 262144 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;

const int MAXN = 2000001;  // 1-based

int N;
ll A[MAXN];

struct Node {
	ll sum;   // Sum tag
	ll max1;  // Max value
	ll max2;  // Second Max value
	ll maxc;  // Max value count
	ll min1;  // Min value
	ll min2;  // Second Min value
	ll minc;  // Min value count
} T[MAXN * 4];

void merge(int t) {
	// sum
	T[t].sum = T[t << 1].sum + T[t << 1 | 1].sum;

	// max
	if (T[t << 1].max1 == T[t << 1 | 1].max1) {
		T[t].max1 = T[t << 1].max1;
		T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max2);
		T[t].maxc = T[t << 1].maxc + T[t << 1 | 1].maxc;
	} else {
		if (T[t << 1].max1 > T[t << 1 | 1].max1) {
			T[t].max1 = T[t << 1].max1;
			T[t].max2 = max(T[t << 1].max2, T[t << 1 | 1].max1);
			T[t].maxc = T[t << 1].maxc;
		} else {
			T[t].max1 = T[t << 1 | 1].max1;
			T[t].max2 = max(T[t << 1].max1, T[t << 1 | 1].max2);
			T[t].maxc = T[t << 1 | 1].maxc;
		}
	}

	// min
	if (T[t << 1].min1 == T[t << 1 | 1].min1) {
		T[t].min1 = T[t << 1].min1;
		T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min2);
		T[t].minc = T[t << 1].minc + T[t << 1 | 1].minc;
	} else {
		if (T[t << 1].min1 < T[t << 1 | 1].min1) {
			T[t].min1 = T[t << 1].min1;
			T[t].min2 = min(T[t << 1].min2, T[t << 1 | 1].min1);
			T[t].minc = T[t << 1].minc;
		} else {
			T[t].min1 = T[t << 1 | 1].min1;
			T[t].min2 = min(T[t << 1].min1, T[t << 1 | 1].min2);
			T[t].minc = T[t << 1 | 1].minc;
		}
	}
}

// corresponds to a chmin update
void push_max(int t, ll v, bool l) {
	if (v >= T[t].max1) { return; }
	T[t].sum -= T[t].max1 * T[t].maxc;
	T[t].max1 = v;
	T[t].sum += T[t].max1 * T[t].maxc;
	if (l) {
		T[t].min1 = T[t].max1;
	} else {
		if (v <= T[t].min1) {
			T[t].min1 = v;
		} else if (v < T[t].min2) {
			T[t].min2 = v;
		}
	}
}

// corresponds to a chmax update
void push_min(int t, ll v, bool l) {
	if (v <= T[t].min1) { return; }
	T[t].sum -= T[t].min1 * T[t].minc;
	T[t].min1 = v;
	T[t].sum += T[t].min1 * T[t].minc;
	if (l) {
		T[t].max1 = T[t].min1;
	} else {
		if (v >= T[t].max1) {
			T[t].max1 = v;
		} else if (v > T[t].max2) {
			T[t].max2 = v;
		}
	}
}

void pushdown(int t, int tl, int tr) {
	if (tl == tr) return;
	// sum
	int tm = (tl + tr) >> 1;
	// max
	push_max(t << 1, T[t].max1, tl == tm);
	push_max(t << 1 | 1, T[t].max1, tm + 1 == tr);

	// min
	push_min(t << 1, T[t].min1, tl == tm);
	push_min(t << 1 | 1, T[t].min1, tm + 1 == tr);
}

void build(int t = 1, int tl = 0, int tr = N - 1) {
	if (tl == tr) {
		T[t].sum = T[t].max1 = T[t].min1 = A[tl];
		T[t].maxc = T[t].minc = 1;
		T[t].max2 = -1e18;
		T[t].min2 = 1e18;
		return;
	}

	int tm = (tl + tr) >> 1;
	build(t << 1, tl, tm);
	build(t << 1 | 1, tm + 1, tr);
	merge(t);
}

void update_chmin(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l || v >= T[t].max1) { return; }
	if (l <= tl && tr <= r && v > T[t].max2) {
		push_max(t, v, tl == tr);
		return;
	}
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	update_chmin(l, r, v, t << 1, tl, tm);
	update_chmin(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}

void update_chmax(int l, int r, ll v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l || v <= T[t].min1) { return; }
	if (l <= tl && tr <= r && v < T[t].min2) {
		push_min(t, v, tl == tr);
		return;
	}
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	update_chmax(l, r, v, t << 1, tl, tm);
	update_chmax(l, r, v, t << 1 | 1, tm + 1, tr);
	merge(t);
}

ll query_sum(int l, int r, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return 0; }
	if (l <= tl && tr <= r) { return T[t].sum; }
	pushdown(t, tl, tr);

	int tm = (tl + tr) >> 1;
	return query_sum(l, r, t << 1, tl, tm) +
	       query_sum(l, r, t << 1 | 1, tm + 1, tr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	N = n;
	build();
	for(int i=0;i<k;i++){
		if(op[i] == 1)update_chmax(left[i], right[i], height[i]);
		else update_chmin(left[i], right[i], height[i]);
	}
	for(int i=0;i<n;i++)finalHeight[i] = query_sum(i, i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 2260 KB Output is correct
5 Correct 10 ms 2308 KB Output is correct
6 Correct 9 ms 2308 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 128 ms 8804 KB Output is correct
3 Correct 85 ms 7852 KB Output is correct
4 Correct 215 ms 23624 KB Output is correct
5 Correct 208 ms 24168 KB Output is correct
6 Correct 252 ms 24096 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 11 ms 2312 KB Output is correct
5 Correct 9 ms 2260 KB Output is correct
6 Correct 9 ms 2260 KB Output is correct
7 Correct 0 ms 312 KB Output is correct
8 Correct 127 ms 8720 KB Output is correct
9 Correct 73 ms 7748 KB Output is correct
10 Correct 198 ms 23608 KB Output is correct
11 Correct 212 ms 24220 KB Output is correct
12 Correct 250 ms 24096 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 132 ms 8652 KB Output is correct
15 Correct 46 ms 5104 KB Output is correct
16 Correct 760 ms 23928 KB Output is correct
17 Correct 401 ms 23864 KB Output is correct
18 Correct 427 ms 23956 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 2260 KB Output is correct
5 Correct 9 ms 2372 KB Output is correct
6 Correct 9 ms 2312 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 131 ms 8788 KB Output is correct
9 Correct 73 ms 7884 KB Output is correct
10 Correct 202 ms 23608 KB Output is correct
11 Correct 210 ms 24188 KB Output is correct
12 Correct 252 ms 24132 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 136 ms 8704 KB Output is correct
15 Correct 45 ms 5068 KB Output is correct
16 Correct 733 ms 23864 KB Output is correct
17 Correct 414 ms 23860 KB Output is correct
18 Correct 442 ms 23872 KB Output is correct
19 Correct 1726 ms 262144 KB Output is correct
20 Correct 1686 ms 262144 KB Output is correct
21 Correct 1733 ms 262144 KB Output is correct
22 Correct 1754 ms 262144 KB Output is correct
23 Correct 1640 ms 262144 KB Output is correct
24 Correct 1645 ms 262144 KB Output is correct
25 Correct 1661 ms 262144 KB Output is correct
26 Correct 1717 ms 262144 KB Output is correct
27 Correct 1687 ms 262144 KB Output is correct
28 Correct 1683 ms 262144 KB Output is correct
29 Correct 1688 ms 262144 KB Output is correct
30 Correct 1653 ms 262144 KB Output is correct