Submission #448363

#	Time	Username	Problem	Language	Result	Execution time	Memory
448363		dutch	Food Court (JOI21_foodcourt)	C++17	100 / 100	415 ms	48364 KiB

foodcourt

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

template<class T> struct SegmentTree{
	T comb(T &x, T &y){	return {max(y[0], x[0] + y[1]), x[1] + y[1]}; }
	int n = 1, i; vector<T> a;
	SegmentTree(int N){ while((n+=n)<N); a.resize(2*n); }
	SegmentTree& operator[](int j){ i=j+n; return *this; }
	void operator=(int v){
		a[i] = {max(v, 0LL), v};
		while(i/=2) a[i] = comb(a[2*i], a[2*i+1]);
	}
	T operator()(int l, int r){
		T lx = {0, 0}, rx = lx;
		for(l+=n, r+=n+1; l<r; l/=2, r/=2){
			if(l & 1) lx = comb(lx, a[l++]);
			if(r & 1) rx = comb(a[--r], rx);
		}
		return comb(lx, rx);
	}
};

struct FenwickTree{
	vector<int> a; int n;
	FenwickTree(int N) : a((n=N)+1) {}
	void add(int i, int v){
		for(++i; i<=n; i+=i&-i) a[i] += v;
	}
	int get(int i){
		int v = 0;
		for(++i; i>=1; i-=i&-i) v += a[i];
		return v;
	}
	int lower_bound(int v){
		int i = 0, j = 1<<19;
		while(j/=2)
			if(i+j<=n && a[i+j]<v) v -= a[i+=j];
		return i;
	}
};

const int LIM = 2.5e5+1;

int n, m, q, groupAt[LIM], ans[LIM];
array<int, 3> a[LIM];
vector<int> qL[LIM], qR[LIM], b[LIM];

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> q;
	for(int i=0, t; i<q; ++i){
		auto &[l, r, k] = a[i];
		cin >> t >> l >> r;
		if(t < 3){
			qL[l].push_back(i);
			qR[r].push_back(i);
		}
		if(t < 2){
			cin >> groupAt[i] >> k;
		}else if(t < 3){
			cin >> k; k = -k;
		}else{
			b[l].push_back(i);
			l = -1;
		}
	}

	SegmentTree<array<int, 2>> st(q);
	FenwickTree F(q);

	for(int i=1; i<=n; ++i){
		for(int &j : qR[i-1]){
			st[j] = 0;
			if(a[j][2] > 0) F.add(j,-a[j][2]);
		}
		for(int &j : qL[i]){
			st[j] = a[j][2];
			if(a[j][2] > 0) F.add(j, a[j][2]);
		}
		for(int &j : b[i]){
			auto v = st(0, j);
			if(v[0] >= a[j][1]){
				ans[j] = groupAt[F.lower_bound(F.get(j) - v[0] + a[j][1])];
			}
		}
	}
	for(int i=0; i<q; ++i){
		if(a[i][0] < 0) cout << ans[i] << '\n';
	}
}

• 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