oj.uz

Submission #959646

# Submission time Handle Problem Language Result Execution time Memory
959646 2024-04-08T14:59:01 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 1391 ms 168152 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

using ll = int;

const int MAXN = 2e6;  // 1-based

int N;

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 != -INT_MAX) { T[t].max2 += v; }
	T[t].min1 += v;
	if (T[t].min2 != INT_MAX) { 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 = 0;
		T[t].maxc = T[t].minc = 1;
		T[t].max2 = -INT_MAX;
		T[t].min2 = INT_MAX;
		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 NN, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N = NN;

  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 0 ms 348 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 9 ms 1672 KB Output is correct
5 Correct 7 ms 1672 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 99 ms 11764 KB Output is correct
3 Correct 62 ms 7156 KB Output is correct
4 Correct 171 ms 22372 KB Output is correct
5 Correct 175 ms 22708 KB Output is correct
6 Correct 209 ms 22008 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 8 ms 1676 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 104 ms 11548 KB Output is correct
9 Correct 73 ms 8152 KB Output is correct
10 Correct 165 ms 22256 KB Output is correct
11 Correct 177 ms 22884 KB Output is correct
12 Correct 215 ms 17552 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 101 ms 8020 KB Output is correct
15 Correct 36 ms 2984 KB Output is correct
16 Correct 641 ms 17244 KB Output is correct
17 Correct 333 ms 17264 KB Output is correct
18 Correct 341 ms 17084 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 8 ms 1584 KB Output is correct
5 Correct 7 ms 1628 KB Output is correct
6 Correct 7 ms 1624 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 96 ms 8272 KB Output is correct
9 Correct 62 ms 5792 KB Output is correct
10 Correct 160 ms 17008 KB Output is correct
11 Correct 180 ms 17492 KB Output is correct
12 Correct 212 ms 17476 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 105 ms 8068 KB Output is correct
15 Correct 36 ms 3064 KB Output is correct
16 Correct 625 ms 17244 KB Output is correct
17 Correct 337 ms 17244 KB Output is correct
18 Correct 369 ms 17232 KB Output is correct
19 Correct 1332 ms 168044 KB Output is correct
20 Correct 1347 ms 165820 KB Output is correct
21 Correct 1324 ms 168152 KB Output is correct
22 Correct 1320 ms 165652 KB Output is correct
23 Correct 1302 ms 165508 KB Output is correct
24 Correct 1334 ms 165556 KB Output is correct
25 Correct 1345 ms 165528 KB Output is correct
26 Correct 1391 ms 168144 KB Output is correct
27 Correct 1364 ms 168124 KB Output is correct
28 Correct 1323 ms 165604 KB Output is correct
29 Correct 1341 ms 165580 KB Output is correct
30 Correct 1315 ms 165624 KB Output is correct