oj.uz

Submission #722615

# Submission time Handle Problem Language Result Execution time Memory
722615 2023-04-12T12:42:41 Z penguin133 Wall (IOI14_wall) C++17
100 / 100
 1623 ms 145920 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 = int;

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);
}

Compilation message

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:122:15: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
  122 |   T[t].max2 = -1e18;
      |               ^~~~~
wall.cpp:123:15: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
  123 |   T[t].min2 = 1e18;
      |               ^~~~

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 368 KB Output is correct
4 Correct 10 ms 1392 KB Output is correct
5 Correct 9 ms 1364 KB Output is correct
6 Correct 9 ms 1384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 133 ms 8580 KB Output is correct
3 Correct 74 ms 5720 KB Output is correct
4 Correct 251 ms 16176 KB Output is correct
5 Correct 213 ms 16716 KB Output is correct
6 Correct 273 ms 16784 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 324 KB Output is correct
3 Correct 3 ms 320 KB Output is correct
4 Correct 11 ms 1396 KB Output is correct
5 Correct 9 ms 1340 KB Output is correct
6 Correct 9 ms 1340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 144 ms 8408 KB Output is correct
9 Correct 100 ms 5740 KB Output is correct
10 Correct 221 ms 16264 KB Output is correct
11 Correct 286 ms 16708 KB Output is correct
12 Correct 274 ms 16716 KB Output is correct
13 Correct 1 ms 308 KB Output is correct
14 Correct 158 ms 8320 KB Output is correct
15 Correct 46 ms 2872 KB Output is correct
16 Correct 794 ms 16388 KB Output is correct
17 Correct 411 ms 16420 KB Output is correct
18 Correct 408 ms 16472 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 11 ms 1336 KB Output is correct
5 Correct 8 ms 1348 KB Output is correct
6 Correct 11 ms 1396 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 128 ms 8584 KB Output is correct
9 Correct 76 ms 5836 KB Output is correct
10 Correct 189 ms 16156 KB Output is correct
11 Correct 207 ms 16724 KB Output is correct
12 Correct 249 ms 16832 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 135 ms 8432 KB Output is correct
15 Correct 44 ms 2848 KB Output is correct
16 Correct 733 ms 16504 KB Output is correct
17 Correct 404 ms 16452 KB Output is correct
18 Correct 404 ms 16544 KB Output is correct
19 Correct 1607 ms 142084 KB Output is correct
20 Correct 1592 ms 140676 KB Output is correct
21 Correct 1598 ms 145740 KB Output is correct
22 Correct 1595 ms 140804 KB Output is correct
23 Correct 1592 ms 140520 KB Output is correct
24 Correct 1581 ms 140736 KB Output is correct
25 Correct 1577 ms 140768 KB Output is correct
26 Correct 1592 ms 145552 KB Output is correct
27 Correct 1592 ms 145920 KB Output is correct
28 Correct 1576 ms 140772 KB Output is correct
29 Correct 1623 ms 140768 KB Output is correct
30 Correct 1589 ms 140740 KB Output is correct