oj.uz

Submission #1025664

# Submission time Handle Problem Language Result Execution time Memory
1025664 2024-07-17T08:36:04 Z toan2602 Meteors (POI11_met) C++14
100 / 100
 1491 ms 60504 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20316 KB Output is correct
2 Correct 4 ms 20316 KB Output is correct
3 Correct 4 ms 20312 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20316 KB Output is correct
2 Correct 4 ms 20316 KB Output is correct
3 Correct 4 ms 20316 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 26388 KB Output is correct
2 Correct 83 ms 26960 KB Output is correct
3 Correct 64 ms 27400 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 26924 KB Output is correct
2 Correct 72 ms 27144 KB Output is correct
3 Correct 99 ms 27276 KB Output is correct
4 Correct 16 ms 23644 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 26708 KB Output is correct
2 Correct 67 ms 27212 KB Output is correct
3 Correct 36 ms 23636 KB Output is correct
4 Correct 72 ms 27736 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 26332 KB Output is correct
2 Correct 84 ms 26916 KB Output is correct
3 Correct 60 ms 26448 KB Output is correct
4 Correct 94 ms 27756 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1222 ms 44584 KB Output is correct
2 Correct 741 ms 38528 KB Output is correct
3 Correct 208 ms 34516 KB Output is correct
4 Correct 1491 ms 58916 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1050 ms 44064 KB Output is correct
2 Correct 674 ms 38608 KB Output is correct
3 Correct 143 ms 31448 KB Output is correct
4 Correct 1207 ms 60504 KB Output is correct