Submission #521514

#	Time	Username	Problem	Language	Result	Execution time	Memory
521514		amunduzbaev	Food Court (JOI21_foodcourt)	C++14	0 / 100	885 ms	61944 KiB

foodcourt

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

#define ar array
#define int long long

const int N = 25e4 + 5;

struct node{
	int t, l, r, c, k, a, b;
};
struct BIT{
	int tree[N<<2], p[2][N<<2];
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		tree[x<<1] += p[0][x], tree[x<<1|1] += p[0][x];
		p[0][x<<1] += p[0][x], p[0][x<<1|1] += p[0][x];
		p[1][x<<1] += p[0][x], p[1][x<<1|1] += p[0][x];
		tree[x<<1] = max(tree[x<<1], p[1][x]);
		p[1][x<<1] = max(p[1][x<<1], p[1][x]);
		p[0][x<<1] = max(p[0][x<<1], p[1][x]);
		tree[x<<1|1] = max(tree[x<<1|1], p[1][x]);
		p[1][x<<1|1] = max(p[1][x<<1|1], p[1][x]);
		p[0][x<<1|1] = max(p[0][x<<1|1], p[1][x]);
		p[0][x] = 0, p[1][x] = -1e18;
	}
	
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		push(x, lx, rx);
		if(lx >= l && rx <= r){
			tree[x] += v;
			p[0][x] += v, p[1][x] += v;
			return;
		} int m = (lx + rx) >> 1;
		add(l, r, v, lx, m, x<<1), 
		add(l, r, v, m+1, rx, x<<1|1);
		tree[x] = max(tree[x<<1], tree[x<<1|1]);
	}
	
	void umax(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		push(x, lx, rx);
		if(lx >= l && rx <= r){
			tree[x] = max(tree[x], v);
			p[1][x] = max(p[1][x], v);
			return;
		} int m = (lx + rx) >> 1;
		umax(l, r, v, lx, m, x<<1), 
		umax(l, r, v, m+1, rx, x<<1|1);
		tree[x] = max(tree[x<<1], tree[x<<1|1]);
	}
	
	int get(int i, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return tree[x];
		push(x, lx, rx);
		int m = (lx + rx) >> 1;
		if(i <= m) return get(i, lx, m, x<<1);
		else return get(i, m+1, rx, x<<1|1);
	}
}cur, tot;

struct ST2{
	ar<int, 2> tree[N<<2];
	int p[N<<2];
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		tree[x<<1][0] += p[x], tree[x<<1|1][0] += p[x];
		p[x<<1] += p[x], p[x<<1|1] += p[x];
		p[x] = 0;
	}
	
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = {v, i}; return; }
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
	}
	
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			tree[x][0] += v;
			p[x] += v; return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x<<1), 
		add(l, r, v, m+1, rx, x<<1|1);
		tree[x] = min(tree[x<<1], tree[x<<1|1]);
	}
	
	ar<int, 2> get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return {(int)1e18, (int)1e18};
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		return min(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}tree;

int res[N], pos[N];
vector<int> qq[N];
node a[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	memset(cur.p[1], 128, sizeof cur.p[1]);
	
	int n, m, q; cin>>n>>m>>q;
	for(int i=0;i<q;i++){
		cin>>a[i].t;
		if(a[i].t == 1){
			cin>>a[i].l>>a[i].r>>a[i].c>>a[i].k;
			cur.add(a[i].l, a[i].r, a[i].k);
			tot.add(a[i].l, a[i].r, a[i].k);
		} if(a[i].t == 2){
			cin>>a[i].l>>a[i].r>>a[i].k;
			cur.add(a[i].l, a[i].r, -a[i].k);
			cur.umax(a[i].l, a[i].r, 0);
		} if(a[i].t == 3){
			cin>>a[i].a>>a[i].b;
			int c = cur.get(a[i].a), t = tot.get(a[i].a) - c;
			if(a[i].b > c) res[i] = 0;
			else {
				qq[a[i].a].push_back(i);
				pos[i] = t + a[i].b;
			}
		}
	}
	
	for(int i=1;i<=n;i++){
		sort(qq[i].begin(), qq[i].end(), [&](int i, int j){
			return (pos[i] > pos[j]);
		});
		
		if(qq[i].empty()) tree.sett(i, 1e18);
		else tree.sett(i, pos[qq[i].back()]);
	}
	
	for(auto x : a){
		if(x.t != 1) continue;
		tree.add(x.l, x.r, -x.k);
		auto mn = tree.get(x.l, x.r);
		while(mn[0] <= 0){
			int i = mn[1];
			res[qq[i].back()] = x.c;
			qq[i].pop_back();
			if(qq[i].empty()) tree.sett(i, 1e18);
			else tree.sett(i, pos[qq[i].back()]);
			mn = tree.get(x.l, x.r);
		}
	}
	
	for(int i=0;i<q;i++){
		if(a[i].t == 3) cout<<res[i]<<"\n";
	} cout<<"\n";
}

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