oj.uz

Submission #561657

# Submission time Handle Problem Language Result Execution time Memory
561657 2022-05-13T10:29:59 Z DanShaders Fish 2 (JOI22_fish2) C++17
5 / 100
 19 ms 468 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 512, INF = 0x3f3f3f3f;

pair<int, int> t[2 * N];
int mod[2 * N];

pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
	if (a.x == b.x) {
		return {a.x, a.y + b.y};
	}
	return min(a, b);
}

void tapply(int i, int x) {
	t[i].x += x;
	mod[i] += x;
}

void tpush(int i) {
	if (mod[i]) {
		tapply(2 * i + 1, mod[i]);
		tapply(2 * i + 2, mod[i]);
		mod[i] = 0;
	}
}

void tpull(int i) {
	t[i] = merge(t[2 * i + 1], t[2 * i + 2]);
}

void tadd(int ql, int qr, int x, int ci = 0, int cl = 0, int cr = N) {
	if (ql <= cl && cr <= qr) {
		tapply(ci, x);
		return;
	}
	if (qr <= cl || cr <= ql) {
		return;
	}
	int mid = (cl + cr) / 2;
	tpush(ci);
	tadd(ql, qr, x, 2 * ci + 1, cl, mid);
	tadd(ql, qr, x, 2 * ci + 2, mid, cr);
	tpull(ci);
}

int left_[N], right_[N];
ll pref[N];
pair<int, int> go[N];
int balance[N];
 
int get(int *a, int n) {
	fill(all(t), pair{0, 0});
	for (int i = 0; i < n; ++i) {
		t[N - 1 + i] = {0, 1};
	}
	for (int i = N - 1; i--; ) {
		t[i] = merge(t[2 * i + 1], t[2 * i + 2]);
		mod[i] = 0;
	}

	for (int i = 0; i < n; ++i) {
		pref[i + 1] = pref[i] + a[i];
	}
	for (int i = 0; i < n; ++i) {
		left_[i] = i - 1;
		while (left_[i] >= 0 && pair{a[left_[i]], left_[i]} < pair{a[i], i}) {
			left_[i] = left_[left_[i]];
		}
	}
	for (int i = n; i--; ) {
		right_[i] = i + 1;
		while (right_[i] < n && pair{a[right_[i]], right_[i]} < pair{a[i], i}) {
			right_[i] = right_[right_[i]];
		}
	}
	fill(balance, balance + n + 1, 0);
	
	auto ai = [&](int i) {
		if (i < 0 || i >= n) {
			return +INF;
		}
		return a[i];
	};
 
	for (int i = 0; i < n; ++i) {
		int lef = left_[i], rig = right_[i];
		if (pref[rig] - pref[lef + 1] < min(ai(lef), ai(rig)) && (lef != -1 || rig != n)) {
			tadd(lef + 1, rig, 1);
		}
	}
	return t[0].y;
}

int a[N];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	int queries;
	cin >> queries;
	while (queries--) {
		int type, l, r;
		cin >> type >> l >> r;
		if (type == 1) {
			a[l - 1] = r;
		} else {
			cout << get(a + l - 1, r - l + 1) << "\n";
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 8 ms 328 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 9 ms 340 KB Output is correct
9 Correct 12 ms 348 KB Output is correct
10 Correct 4 ms 336 KB Output is correct
11 Correct 7 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 10 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 7 ms 352 KB Output is correct
16 Correct 8 ms 348 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 8 ms 324 KB Output is correct
19 Correct 5 ms 340 KB Output is correct
20 Correct 19 ms 364 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 2 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 8 ms 328 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 9 ms 340 KB Output is correct
9 Correct 12 ms 348 KB Output is correct
10 Correct 4 ms 336 KB Output is correct
11 Correct 7 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 10 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 7 ms 352 KB Output is correct
16 Correct 8 ms 348 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 8 ms 324 KB Output is correct
19 Correct 5 ms 340 KB Output is correct
20 Correct 19 ms 364 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Runtime error 2 ms 468 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 2 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 2 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 8 ms 328 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 9 ms 340 KB Output is correct
9 Correct 12 ms 348 KB Output is correct
10 Correct 4 ms 336 KB Output is correct
11 Correct 7 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 10 ms 340 KB Output is correct
14 Correct 3 ms 340 KB Output is correct
15 Correct 7 ms 352 KB Output is correct
16 Correct 8 ms 348 KB Output is correct
17 Correct 4 ms 340 KB Output is correct
18 Correct 8 ms 324 KB Output is correct
19 Correct 5 ms 340 KB Output is correct
20 Correct 19 ms 364 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Runtime error 2 ms 468 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -