oj.uz

Submission #426123

# Submission time Handle Problem Language Result Execution time Memory
426123 2021-06-13T14:23:52 Z 8e7 Food Court (JOI21_foodcourt) C++14
21 / 100
 870 ms 56376 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) {
				ll rem = bst.sum[1] + bst.tag[1] * q - (pnt - val);
				j.ss += rem;
				//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 12 ms 18252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 26860 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 596 ms 51192 KB Output is correct
2 Correct 527 ms 47752 KB Output is correct
3 Correct 736 ms 52720 KB Output is correct
4 Correct 610 ms 49472 KB Output is correct
5 Correct 608 ms 49384 KB Output is correct
6 Correct 831 ms 54940 KB Output is correct
7 Correct 210 ms 48204 KB Output is correct
8 Correct 232 ms 48096 KB Output is correct
9 Correct 851 ms 54068 KB Output is correct
10 Correct 870 ms 54096 KB Output is correct
11 Correct 751 ms 49332 KB Output is correct
12 Correct 759 ms 53420 KB Output is correct
13 Correct 697 ms 49856 KB Output is correct
14 Correct 684 ms 53496 KB Output is correct
15 Correct 775 ms 53312 KB Output is correct
16 Correct 635 ms 53440 KB Output is correct
17 Correct 751 ms 53340 KB Output is correct
18 Correct 846 ms 51448 KB Output is correct
19 Correct 712 ms 53460 KB Output is correct
20 Correct 786 ms 51860 KB Output is correct
21 Correct 780 ms 53448 KB Output is correct
22 Correct 799 ms 53332 KB Output is correct
23 Correct 802 ms 53476 KB Output is correct
24 Correct 826 ms 53452 KB Output is correct
25 Correct 514 ms 52372 KB Output is correct
26 Correct 565 ms 52976 KB Output is correct
27 Correct 562 ms 56376 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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