oj.uz

Submission #426058

# Submission time Handle Problem Language Result Execution time Memory
426058 2021-06-13T13:24:44 Z 8e7 Food Court (JOI21_foodcourt) C++14
21 / 100
 582 ms 47828 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){ cout << a << " ";debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 250005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
//using namespace __gnu_pbds;

struct segtree{
	ll seg[4 * maxn], tag[4 * maxn];
	void modify(int cur, int l, int r, int ql, int qr, ll val) {
		if (r <= l || qr <= l || ql >= r) return;
		if (ql <= l && qr >= r) {
			tag[cur] += val;
			return;
		}
		int mid = (l + r) / 2;
		modify(cur * 2, l, mid, ql, qr, val);
		modify(cur * 2 + 1, mid, r, ql, qr, val);
		seg[cur] = min(seg[cur * 2] + tag[cur * 2], seg[cur * 2 + 1] + tag[cur * 2 + 1]);
	}
	ll query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || qr <= l || ql >= r) return 1LL<<60;
		if (ql <= l && qr >= r) return seg[cur] + tag[cur];
		int mid = (l + r) / 2;
		return tag[cur] + min(query(cur * 2, l, mid, ql, qr), query(cur * 2 + 1, mid, r, ql, qr));	
	}
} se;
vector<pii> query[maxn], mod[maxn], arr[maxn]; 
int col[maxn];
ll ans[maxn];
int main() {
	io
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> qind;
	for (int i = 0;i < q;i++) {
		int type;
		cin >> type;
		if (type == 1) {
			ll l, r, c, k;
			cin >> l >> r >> c >> k;
			col[i] = c;
			arr[l].push_back({i, k});
			arr[r + 1].push_back({i, -k});
			mod[l].push_back({i, k});
			mod[r + 1].push_back({i, -k});
		} else if (type == 2) {
			ll l, r, k;
			cin >> l >> r >> k;
			mod[l].push_back({i, -k});
			mod[r + 1].push_back({i, k});
		} else {
			ll ind, num;
			cin >> ind >> num;
			query[ind].push_back({i, num});
			qind.push_back(i);
		}
	}
	for (int i = 1;i <= n;i++) {
		for (auto j:mod[i]) {
			se.modify(1, 0, q, j.ff, q, j.ss);			
		}
		for (auto j:query[i]) {
			ll val = min(0LL, se.query(1, 0, q, 0, j.ff + 1));
			ll pnt = se.query(1, 0, q, j.ff, j.ff + 1);
			//debug(j.ff, j.ss, pnt, val);
			if (pnt - val >= j.ss) {
				ans[j.ff] = 1;
			} else {
				ans[j.ff] = 0;
			}
		}
	}
	for (int i:qind) {
		cout << ans[i] << "\n";
	}
}
/*
3 4 7
1 1 2 1 1
1 1 3 4 1
2 2 3 1
2 1 3 1
1 1 2 2 1
3 1 1
3 3 2

4 1 7
1 1 3 1 5
1 2 4 1 3
2 1 3 5 
1 3 4 1 7
3 3 4
3 2 3
3 1 1
   */

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 42900 KB Output is correct
2 Correct 359 ms 39096 KB Output is correct
3 Correct 547 ms 44276 KB Output is correct
4 Correct 446 ms 40784 KB Output is correct
5 Correct 416 ms 41024 KB Output is correct
6 Correct 525 ms 46464 KB Output is correct
7 Correct 176 ms 39540 KB Output is correct
8 Correct 201 ms 39584 KB Output is correct
9 Correct 498 ms 45500 KB Output is correct
10 Correct 565 ms 45444 KB Output is correct
11 Correct 478 ms 44352 KB Output is correct
12 Correct 527 ms 44948 KB Output is correct
13 Correct 562 ms 44424 KB Output is correct
14 Correct 582 ms 44940 KB Output is correct
15 Correct 503 ms 44828 KB Output is correct
16 Correct 527 ms 44928 KB Output is correct
17 Correct 556 ms 44864 KB Output is correct
18 Correct 538 ms 44628 KB Output is correct
19 Correct 512 ms 44952 KB Output is correct
20 Correct 490 ms 44740 KB Output is correct
21 Correct 513 ms 44860 KB Output is correct
22 Correct 498 ms 44860 KB Output is correct
23 Correct 530 ms 44848 KB Output is correct
24 Correct 580 ms 44864 KB Output is correct
25 Correct 371 ms 43964 KB Output is correct
26 Correct 362 ms 44460 KB Output is correct
27 Correct 423 ms 47828 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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