제출 #542625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
542625		jinhan814	새로운 문제 (POI11_met)	C++17	0 / 100	982 ms	20100 KiB

met

#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';
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13