Submission #1013430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013430		0npata	Food Court (JOI21_foodcourt)	C++17	100 / 100	224 ms	56488 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;

#define vec vector
#define int long long

struct SegNode {
	int tot = 0;
	int rem = 0;
	int pot = 0;

	/// Other should always be the right node
	SegNode merge(SegNode other) {
		int er = min(other.pot, rem);

		return {tot + other.tot, other.rem + rem - er, pot + other.pot - er};
	}

};

struct SegTree {
	vec<SegNode> data;
	int n;

	SegTree(int in) {
		n = 1;
		while(n < in) n *= 2;
		data = vec<SegNode>(n*2);
	}

	SegNode query(int l, int r, int i = 1, int ll = 0, int rr = -1) {
		if(rr == -1) rr = n;

		if(rr <= l || ll >= r) return {};
		if(ll >= l && rr <= r) return data[i];

		int m = (ll+rr)/2;
		return query(l, r, i*2, ll, m).merge(query(l, r, i*2 + 1, m, rr));
	}

	void set(int i, SegNode val) {
		i += n;
		data[i] = val;
		while(i>1) {
			i /= 2;
			data[i] = data[i*2].merge(data[i*2+1]);
		}
	}

	int get_kth(int k, int i = 1) {
		if(k >= data[i].tot) return n+1;
		if(i * 2 >= data.size()) {
			return i-n;
		}
		if(k < data[i*2].tot) return get_kth(k, i*2);
		return get_kth(k-data[i*2].tot, i*2+1);
	}
};

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m, q;
	cin >> n >> m >> q;

	vec<int> ans(q, -1);
	vec<int> vals(q, -1);

	vec<vec<pair<int, int>>> quer(n);
	vec<vec<pair<int, SegNode>>> ls(n);
	vec<vec<int>> rs(n);

	for(int i = 0; i<q; i++) {
		int qt;
		cin >> qt;
		if(qt == 1) {
			int l, r, c, k;
			cin >> l >> r >> c >> k;
			ls[l-1].push_back({i, {k, k, 0}});
			rs[r-1].push_back(i);
			vals[i] = c;
		}
		else if(qt == 2) {
			int l, r, k;
			cin >> l >> r >> k;
			ls[l-1].push_back({i, {0, 0, k}});
			rs[r-1].push_back(i);
		}
		else {
			assert(qt == 3);
			int a, b;
			cin >> a >> b;
			quer[a-1].push_back({i, b-1});
		}
	}

	SegTree st(q);

	for(int i = 0; i<n; i++) {
		for(auto [t, sn] : ls[i]) {
			st.set(t, sn);
		}

		for(auto [t, j] : quer[i]) {
			SegNode res = st.query(0, t+1);
			int er = res.tot - res.rem;
			//cerr << "ER: " << er << '\n';
			//cerr << "J: " << j << '\n';
			int vt = st.get_kth(er+j);
			//cerr << "TOT: " << res.tot << '\n';
			//cerr << "VT: " << vt << '\n';
			if(vt > t) {
				ans[t] = 0;
			}
			else {
				assert(vals[vt] != -1);
				ans[t] = vals[vt];
			}
		}

		for(int t : rs[i]) {
			st.set(t, {});
		}
	}

	for(int i = 0; i<q; i++) {
		if(ans[i] == -1) continue;
		cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

foodcourt.cpp: In member function 'long long int SegTree::get_kth(long long int, long long int)':
foodcourt.cpp:52:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<SegNode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   if(i * 2 >= data.size()) {
      |      ~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11