Submission #1025664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025664		toan2602	Meteors (POI11_met)	C++14	100 / 100	1491 ms	60504 KiB

met

#include<bits/stdc++.h>

using namespace std;
#define int long long
int n, m, o[300005], p[300005], qr, l[300005], r[300005], x[300005], sum[300005], ans[300005];
vector<int> pos[300005];
struct Segtree {
	int val[300005];
	void update(int l, int r, int nw) {
		while(l <= m+1) {
			val[l] += nw;
			l += l & -l;
		}
		nw = -nw, r++;
		while(r <= m+1) {
			val[r] += nw;
			r += r & -r;
		}
	}
	int get(int pos) {
		int res = 0;
		while(pos > 0) {
			res += val[pos];
			pos -= pos & -pos;
		}
		return res;
	}
	void reset() {
		for (int i = 1; i <= m; i++) val[i] = 0;
	}
} tree;
struct NODE {
	int l, r;
	vector<int> v;
};
queue<NODE> q;
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> o[i], pos[o[i]].push_back(i);
	for (int i = 1; i <= n; i++) cin >> p[i];
	cin >> qr;
	for (int i = 1; i <= qr; i++) {
		cin >> l[i] >> r[i] >> x[i];
		if(l[i] <= r[i]) tree.update(l[i], r[i], x[i]);
		else tree.update(l[i], m, x[i]), tree.update(1, r[i], x[i]);
	}
	vector<int> init;
	for (int i = 1; i <= m; i++) sum[o[i]] += (sum[o[i]] < 1e9 ? tree.get(i) : 0);
	for (int i = 1; i <= n; i++) if(sum[i] >= p[i]) init.push_back(i);
	q.push({1, qr, init});
	tree.reset();
	memset(ans, -1, sizeof(ans));
	while(!q.empty()) {
		NODE cur = q.front();
		q.pop();
		int cl = cur.l, cr = cur.r, mid = (cl + cr) / 2;
		if(cr-cl==0) {
			int i = cl;
			if(l[i] <= r[i]) tree.update(l[i], r[i], x[i]);
			else tree.update(l[i], m, x[i]), tree.update(1, r[i], x[i]);
			for (int i: cur.v) ans[i] = cl;
			continue;
		}
		if(cl == 1) tree.reset();
		for (int i = cl; i <= mid; i++) {
			if(l[i] <= r[i]) tree.update(l[i], r[i], x[i]);
			else tree.update(l[i], m, x[i]), tree.update(1, r[i], x[i]);
		}
		vector<int> L, R;
		for (int i: cur.v) {
			int val = 0;
			for (int j: pos[i]) {val += tree.get(j); if(val >= 1e9) break;}
			if(val >= p[i]) L.push_back(i); else R.push_back(i);
		}
		for (int i = mid+1; i <= cr; i++) {
			if(l[i] <= r[i]) tree.update(l[i], r[i], x[i]);
			else tree.update(l[i], m, x[i]), tree.update(1, r[i], x[i]);
		}
		q.push({cl, mid, L});
		q.push({mid+1, cr, R});
	}
	for (int i = 1; i <= n; i++) if(ans[i]==-1) cout << "NIE\n"; else cout << ans[i] << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen("input.inp","r")){
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	}
	int t = 1;
	// cin >> t;
	while(t--) {
		solve();
	}
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:88:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   freopen("input.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:89:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   freopen("output.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13