oj.uz

Submission #793578

# Submission time Handle Problem Language Result Execution time Memory
793578 2023-07-26T04:12:06 Z GEN 이지후(#10094) Triangle Collection (CCO23_day2problem3) C++17
0 / 25
 21 ms 360 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXN = 2005;

struct fen {
	pi tree[MAXN];
	void clear() { fill(tree, tree + MAXN, pi{int(1e9), -1}); }
	void add(int x, pi v) {
		for (int i = x + 2; i < MAXN; i += i & -i)
			tree[i] = min(tree[i], v);
	}
	pi query(int x) {
		pi ret{int(1e9), -1};
		for (int i = x + 2; i; i -= i & -i)
			ret = min(ret, tree[i]);
		return ret;
	}
} bit;
pi dp[MAXN][MAXN];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for (auto &x : a)
		cin >> x;
	auto solve = [&]() {
		lint ans = 0;
		vector<int> b(n);
		for (int i = n - 1; i >= 0; i--) {
			b[i] = a[i] % 3;
			ans += a[i] / 3;
		}
		queue<int> que;
		for (int i = n; i >= 1; i--) {
			if (b[i - 1] == 1) {
				que.push(i);
				b[i - 1] = 0;
			} else if (b[i - 1] == 2) {
				while (sz(que) && que.front() > 2 * i - 1)
					que.pop();
				if (sz(que)) {
					que.pop();
					b[i - 1] = 0;
					ans++;
				}
			}
		}
		while (sz(que))
			que.pop();
		int prv = -1;
		for (int i = 1; i <= n; i++) {
			if (b[i - 1] == 2) {
				if (prv != -1 && 2 * prv - 1 >= i)
					ans++;
				else
					prv = i;
			}
		}
		return ans;
	};
	while (q--) {
		int i, d;
		cin >> i >> d;
		a[i - 1] += d;
		cout << solve() << "\n";
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -