oj.uz

Submission #779821

# Submission time Handle Problem Language Result Execution time Memory
779821 2023-07-12T00:00:46 Z YassirSalama Wall (IOI14_wall) C++14
61 / 100
 620 ms 19352 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int MAXN = 200001;  // 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 1 ms 212 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 1492 KB Output is correct
5 Correct 9 ms 1544 KB Output is correct
6 Correct 7 ms 1544 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 102 ms 10008 KB Output is correct
3 Correct 61 ms 7596 KB Output is correct
4 Correct 193 ms 18528 KB Output is correct
5 Correct 177 ms 18896 KB Output is correct
6 Correct 210 ms 19352 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 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 11 ms 1620 KB Output is correct
5 Correct 7 ms 1536 KB Output is correct
6 Correct 10 ms 1476 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 102 ms 11568 KB Output is correct
9 Correct 60 ms 9172 KB Output is correct
10 Correct 171 ms 18584 KB Output is correct
11 Correct 185 ms 19008 KB Output is correct
12 Correct 211 ms 19340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 105 ms 10044 KB Output is correct
15 Correct 44 ms 3544 KB Output is correct
16 Correct 618 ms 18796 KB Output is correct
17 Correct 396 ms 19040 KB Output is correct
18 Correct 346 ms 19148 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 1544 KB Output is correct
5 Correct 7 ms 1492 KB Output is correct
6 Correct 7 ms 1492 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 103 ms 11564 KB Output is correct
9 Correct 60 ms 9164 KB Output is correct
10 Correct 169 ms 18580 KB Output is correct
11 Correct 172 ms 18888 KB Output is correct
12 Correct 209 ms 19272 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 105 ms 9924 KB Output is correct
15 Correct 36 ms 3536 KB Output is correct
16 Correct 620 ms 18612 KB Output is correct
17 Correct 348 ms 18872 KB Output is correct
18 Correct 403 ms 18912 KB Output is correct
19 Runtime error 147 ms 17680 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -