oj.uz

Submission #793608

# Submission time Handle Problem Language Result Execution time Memory
793608 2023-07-26T04:35:38 Z GEN 이지후(#10094) Triangle Collection (CCO23_day2problem3) C++17
0 / 25
 28 ms 352 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;
		auto b = a;
		queue<int> que;
		for (int i = n; i >= 1; i--) {
			if (b[i - 1] % 2 == 1) {
				que.push(i);
				b[i - 1]--;
			}
			while (sz(que) && que.front() > 2 * i - 1)
				que.pop();
			while (sz(que) && b[i - 1]) {
				que.pop();
				b[i - 1] -= 2;
				ans++;
			}
		}
		lint cnt = 0;
		for (int i = 1; i <= n; i++) {
			cnt += b[i - 1];
		}
		ans += cnt / 3;
		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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 348 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 2 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -