oj.uz

Submission #779823

# Submission time Handle Problem Language Result Execution time Memory
779823 2023-07-12T00:01:43 Z YassirSalama Wall (IOI14_wall) C++14
100 / 100
 1416 ms 158692 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int MAXN = 2000001;  // 1-based
int N;
int A[MAXN];
const int intINF=1e9+7;
struct Node {
	int sum;   // Sum tag
	int max1;  // Max value
	int max2;  // Second Max value
	int maxc;  // Max value count
	int min1;  // Min value
	int min2;  // Second Min value
	int minc;  // Min value count
	int lazy;  // Lazy tag
} 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;
		}
	}
}

void push_add(int t, int tl, int tr, int v) {
	if (v == 0) { return; }
	T[t].sum += (tr - tl + 1) * v;
	T[t].max1 += v;
	if (T[t].max2 != -intINF) { T[t].max2 += v; }
	T[t].min1 += v;
	if (T[t].min2 != intINF) { T[t].min2 += v; }
	T[t].lazy += v;
}

// corresponds to a chmin update
void push_max(int t, int 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, int 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;
	push_add(t << 1, tl, tm, T[t].lazy);
	push_add(t << 1 | 1, tm + 1, tr, T[t].lazy);
	T[t].lazy = 0;

	// 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) {
	T[t].lazy = 0;
	if (tl == tr) {
		T[t].sum = T[t].max1 = T[t].min1 = A[tl];
		T[t].maxc = T[t].minc = 1;
		T[t].max2 = -intINF;
		T[t].min2 = intINF;
		return;
	}

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

void update_add(int l, int r, int v, int t = 1, int tl = 0, int tr = N - 1) {
	if (r < tl || tr < l) { return; }
	if (l <= tl && tr <= r) {
		push_add(t, tl, tr, v);
		return;
	}
	pushdown(t, tl, tr);

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

void update_chmin(int l, int r, int 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, int 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);
}

int 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[]){
	// build(1,0,n-1);
	// memset(A,0,sizeof A);
	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]);
		}
		// update(left[i],right[i],height[i]);
	}
	for(int i=0;i<n;i++){
		int x=query_sum(i,i);
		// cout<<x<<" ";
		finalHeight[i]=x;
	}
	// cout<<endl;
	// query(1,1,n,finalHeight);
	// for(int i=0;i<n;i++){
		// cout<<finalHeight[i]<<" ";
	// }
	// cout<<endl;
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 8 ms 1492 KB Output is correct
5 Correct 7 ms 1452 KB Output is correct
6 Correct 7 ms 1508 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 104 ms 8036 KB Output is correct
3 Correct 58 ms 5676 KB Output is correct
4 Correct 163 ms 16932 KB Output is correct
5 Correct 170 ms 17332 KB Output is correct
6 Correct 206 ms 17380 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 1492 KB Output is correct
5 Correct 7 ms 1452 KB Output is correct
6 Correct 7 ms 1492 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 112 ms 8056 KB Output is correct
9 Correct 59 ms 5652 KB Output is correct
10 Correct 160 ms 16932 KB Output is correct
11 Correct 178 ms 17500 KB Output is correct
12 Correct 211 ms 17384 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 102 ms 8064 KB Output is correct
15 Correct 35 ms 2892 KB Output is correct
16 Correct 593 ms 17100 KB Output is correct
17 Correct 339 ms 17200 KB Output is correct
18 Correct 335 ms 17124 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 9 ms 1452 KB Output is correct
5 Correct 7 ms 1460 KB Output is correct
6 Correct 7 ms 1456 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 107 ms 8048 KB Output is correct
9 Correct 59 ms 5632 KB Output is correct
10 Correct 160 ms 16892 KB Output is correct
11 Correct 169 ms 17376 KB Output is correct
12 Correct 210 ms 17380 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 118 ms 8140 KB Output is correct
15 Correct 36 ms 2976 KB Output is correct
16 Correct 634 ms 17224 KB Output is correct
17 Correct 335 ms 17200 KB Output is correct
18 Correct 359 ms 17124 KB Output is correct
19 Correct 1305 ms 157608 KB Output is correct
20 Correct 1309 ms 156268 KB Output is correct
21 Correct 1309 ms 158692 KB Output is correct
22 Correct 1355 ms 156136 KB Output is correct
23 Correct 1306 ms 156108 KB Output is correct
24 Correct 1312 ms 156212 KB Output is correct
25 Correct 1379 ms 155876 KB Output is correct
26 Correct 1312 ms 158460 KB Output is correct
27 Correct 1327 ms 158392 KB Output is correct
28 Correct 1416 ms 155884 KB Output is correct
29 Correct 1319 ms 155884 KB Output is correct
30 Correct 1325 ms 155876 KB Output is correct