oj.uz

Submission #738970

# Submission time Handle Problem Language Result Execution time Memory
738970 2023-05-09T17:49:54 Z shoryu386 Wall (IOI14_wall) C++17
61 / 100
 769 ms 262144 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
#define llINF (LLONG_MAX/10)
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
	ll 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, ll v) {
	if (v == 0) {
		return;
	}
	T[t].sum += (tr - tl + 1) *v;
	T[t].max1 += v;
	if (T[t].max2 != -llINF) {
		T[t].max2 += v;
	}
	T[t].min1 += v;
	if (T[t].min2 != llINF) {
		T[t].min2 += v;
	}
	T[t].lazy += v;
}

// 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;
	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 = -llINF;
		T[t].min2 = llINF;
		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, ll 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, 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[]){
	for (int x = 0; x < n; x++) A[x] = 0;
	N = n;
	
	build();
	
	for (int x = 0; x < k; x++){
		if (op[x] == 1) update_chmax(left[x], right[x], height[x]);
		else update_chmin(left[x], right[x], height[x]);
	}
	
	for (int x = 0; x < n; x++) finalHeight[x] = query_sum(x, x);
}


/*
int main() {
	int Q;

	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	build();
	for (int q = 0; q < Q; q++) {
		int t; cin >> t;
		if (t == 0) {
			int l, r;
			ll x;
			cin >> l >> r >> x;
			update_chmin(l, r, x);
		} else if (t == 1) {
			int l, r;
			ll x;
			cin >> l >> r >> x;
			update_chmax(l, r, x);
		} else if (t == 2) {
			int l, r;
			ll x;
			cin >> l >> r >> x;
			update_add(l, r, x);
		} else if (t == 3) {
			int l, r;
			cin >> l >> r;
			cout << query_sum(l, r) << '\n';
		}
	}
}
*/

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 3 ms 340 KB Output is correct
4 Correct 10 ms 2516 KB Output is correct
5 Correct 9 ms 2516 KB Output is correct
6 Correct 8 ms 2516 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 125 ms 8088 KB Output is correct
3 Correct 74 ms 7876 KB Output is correct
4 Correct 194 ms 25916 KB Output is correct
5 Correct 216 ms 26336 KB Output is correct
6 Correct 245 ms 26320 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 12 ms 2516 KB Output is correct
5 Correct 10 ms 2624 KB Output is correct
6 Correct 9 ms 2516 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 129 ms 8140 KB Output is correct
9 Correct 78 ms 7888 KB Output is correct
10 Correct 200 ms 25952 KB Output is correct
11 Correct 210 ms 26408 KB Output is correct
12 Correct 255 ms 26348 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 152 ms 8072 KB Output is correct
15 Correct 44 ms 5156 KB Output is correct
16 Correct 769 ms 26184 KB Output is correct
17 Correct 411 ms 26196 KB Output is correct
18 Correct 452 ms 26188 KB Output is correct

Subtask #4
0 / 39.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 11 ms 2556 KB Output is correct
5 Correct 9 ms 2516 KB Output is correct
6 Correct 10 ms 2516 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 142 ms 8084 KB Output is correct
9 Correct 74 ms 7884 KB Output is correct
10 Correct 195 ms 25940 KB Output is correct
11 Correct 217 ms 26332 KB Output is correct
12 Correct 249 ms 26384 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 137 ms 8108 KB Output is correct
15 Correct 42 ms 5168 KB Output is correct
16 Correct 761 ms 26152 KB Output is correct
17 Correct 448 ms 26072 KB Output is correct
18 Correct 426 ms 26176 KB Output is correct
19 Runtime error 264 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -