oj.uz

Submission #426113

# Submission time Handle Problem Language Result Execution time Memory
426113 2021-06-13T14:18:04 Z 8e7 Food Court (JOI21_foodcourt) C++14
34 / 100
 849 ms 58612 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], sum[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]);
		sum[cur] = sum[cur * 2] + tag[cur * 2] * (mid - l) + sum[cur * 2 + 1] + tag[cur * 2 + 1] * (r - mid);
	}
	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));	
	}
	int search(int cur, int l, int r, ll val) { //leftmost index with sum >= val
		//debug(l, r, sum[cur], val);
		if (r <= l) return 0;
		if (r - l == 1) return l;
		int mid = (l + r) / 2;
		if (sum[cur * 2] + (tag[cur * 2] + tag[cur]) * (mid - l) >= val) {
			return search(cur * 2, l, mid, val - tag[cur] * (mid - l));
		} else {
			return search(cur * 2 + 1, mid, r, val - sum[cur * 2] - tag[cur * 2] * (mid - l) - tag[cur] * (r - l));
		}
	}
} se, bst;
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:arr[i]) {
			bst.modify(1, 0, q, j.ff, j.ff + 1, 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(i, j.ss, pnt, val);
			if (pnt - val >= j.ss) {
				//debug(i, j.ss, bst.search(1, 0, q, j.ss));
				ans[j.ff] = col[bst.search(1, 0, q, j.ss)];
				//ans[j.ff] = 1;
			} else {
				ans[j.ff] = 0;
			}
		}
	}
	for (int i:qind) {
		cout << ans[i] << "\n";
	}
}
/*
5 5 9
1 2 3 5 2
1 1 2 2 4
3 2 3
1 1 2 2 4
3 2 5
1 3 4 1 3
3 4 1 
3 5 4
3 3 4

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 18172 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 18172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 27860 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 676 ms 53436 KB Output is correct
2 Correct 511 ms 49728 KB Output is correct
3 Correct 781 ms 54852 KB Output is correct
4 Correct 550 ms 51372 KB Output is correct
5 Correct 522 ms 51412 KB Output is correct
6 Correct 827 ms 56928 KB Output is correct
7 Correct 227 ms 50120 KB Output is correct
8 Correct 227 ms 50152 KB Output is correct
9 Correct 788 ms 56036 KB Output is correct
10 Correct 771 ms 56064 KB Output is correct
11 Correct 735 ms 51360 KB Output is correct
12 Correct 730 ms 55472 KB Output is correct
13 Correct 743 ms 51852 KB Output is correct
14 Correct 705 ms 55492 KB Output is correct
15 Correct 756 ms 55368 KB Output is correct
16 Correct 810 ms 55456 KB Output is correct
17 Correct 750 ms 55412 KB Output is correct
18 Correct 756 ms 53396 KB Output is correct
19 Correct 751 ms 55388 KB Output is correct
20 Correct 758 ms 53828 KB Output is correct
21 Correct 686 ms 55476 KB Output is correct
22 Correct 824 ms 55404 KB Output is correct
23 Correct 849 ms 55468 KB Output is correct
24 Correct 737 ms 55576 KB Output is correct
25 Correct 498 ms 54504 KB Output is correct
26 Correct 511 ms 55032 KB Output is correct
27 Correct 602 ms 58612 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 28028 KB Output is correct
2 Correct 151 ms 28700 KB Output is correct
3 Correct 154 ms 28868 KB Output is correct
4 Correct 129 ms 26868 KB Output is correct
5 Correct 133 ms 28052 KB Output is correct
6 Correct 147 ms 28820 KB Output is correct
7 Correct 79 ms 26512 KB Output is correct
8 Correct 65 ms 26164 KB Output is correct
9 Correct 87 ms 27404 KB Output is correct
10 Correct 87 ms 26540 KB Output is correct
11 Correct 122 ms 28120 KB Output is correct
12 Correct 130 ms 28184 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 18172 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 18172 KB Output isn't correct
2 Halted 0 ms 0 KB -