oj.uz

Submission #542625

# Submission time Handle Problem Language Result Execution time Memory
542625 2022-03-27T08:49:12 Z jinhan814 Meteors (POI11_met) C++17
0 / 100
 982 ms 20100 KB 
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;

using ll = long long;
using pii = pair<int, int>;

struct Query { int l, r, x; };

struct Fenwick {
	ll tree[300'001];
	void Init() { memset(tree, 0, sizeof tree); }
	void Update(int i, int val) {
		for (; i <= 300'000; i += i & -i) tree[i] += val;
	}
	ll Query(int i) {
		ll ret = 0;
		for (; i; i -= i & -i) ret = min(ret + tree[i], ll(2e9));
		return ret;
	}
} FT;

int n, m, q, v[300'001], lo[300'001], hi[300'001];
Query Q[300'001];
vector<int> pos[300'001];

void Update(int l, int r, int x) {
	if (l <= r) FT.Update(l, x), FT.Update(r + 1, -x);
	else Update(l, m, x), Update(1, r, x);
}

void PBS() {
	for (int i = 1; i <= n; i++) lo[i] = 0, hi[i] = q + 1;
	while (1) {
		vector<pii> I;
		for (int i = 1; i <= n; i++) {
			if (lo[i] + 1 == hi[i]) continue;
			I.push_back({ lo[i] + hi[i] >> 1, i });
		}
		if (I.empty()) break;
		sort(I.begin(), I.end());
		FT.Init();
		for (int i = 1, j = 0; i <= q && j < I.size(); i++) {
			Update(Q[i].l, Q[i].r, Q[i].x);
			for (; j < I.size() && I[j].first <= i; j++) {
				const auto [mid, idx] = I[j];
				ll sum = 0;
				for (int i : pos[idx]) sum += FT.Query(i);
				if (sum <= v[idx]) lo[idx] = mid;
				else hi[idx] = mid;
			}
		}
	}
}

int main() {
	fastio;
	cin >> n >> m;
	for (int i = 1, t; i <= m; i++) cin >> t, pos[t].push_back(i);
	for (int i = 1; i <= n; i++) cin >> v[i];
	cin >> q;
	for (int i = 1; i <= q; i++) cin >> Q[i].l >> Q[i].r >> Q[i].x;
	PBS();
	for (int i = 1; i <= q; i++) {
		if (hi[i] == q + 1) cout << "NIE" << '\n';
		else cout << hi[i] << '\n';
	}
}

Compilation message

met.cpp: In function 'void PBS()':
met.cpp:38:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |    I.push_back({ lo[i] + hi[i] >> 1, i });
      |                  ~~~~~~^~~~~~~
met.cpp:43:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int i = 1, j = 0; i <= q && j < I.size(); i++) {
      |                                    ~~^~~~~~~~~~
met.cpp:45:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for (; j < I.size() && I[j].first <= i; j++) {
      |           ~~^~~~~~~~~~

Subtask #1
0 / 12.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 13.0

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

Subtask #8
0 / 13.0

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