Submission #395987

#	Time	Username	Problem	Language	Result	Execution time	Memory
395987		oolimry	Food Court (JOI21_foodcourt)	C++17	0 / 100	1083 ms	28920 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

int n, M, Q;

struct thing{ int v, l, r; };
thing merge(thing a, thing b){
	//if(a.v == b.v and a.r == b.l + 1) return {a.v, a.l, b.r};
	if(a.v > b.v) return b;
	else return a;
}

struct node{
	thing val; lint lazy;
	int s, e, m;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val = {0,s,s}; lazy = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	void apply(lint L){
		val.v += L;
		lazy += L;
	}
	void push(){
		if(s != e){
			l->apply(lazy);
			r->apply(lazy);
			lazy = 0;
		}
	}
	
	void update(int S, int E, lint L){
		push();
		if(s == S and e == E){
			apply(L);
			return;
		}
		if(E <= m) l->update(S, E, L);
		else if(S >= m+1) r->update(S, E, L);
		else l->update(S, m, L), r->update(m+1, E, L);
		
		val = merge(l->val, r->val);
	}
	
	thing query(int S, int E){
		push();
		if(s == S and E == e) return val;
		else if(E <= m) return l->query(S, E);
		else if(S >= m+1) return r->query(S, E);
		else return merge(l->query(S, m), r->query(m+1, E));
	}
} *root;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> M >> Q;
	
	root = new node(1, n);
	
	for(int i = 0;i < Q;i++){
		int t; cin >> t;
		if(t == 1){
			int l, r, c, k; cin >> l >> r >> c >> k;
			root->update(l,r,k);
		}
		else if(t == 2){
			int l, r, k; cin >> l >> r >> k;
			root->update(l,r,-k);
			
			while(true){
				thing small = root->query(1,n);
				if(small.v >= 0) break;
				root->update(small.l, small.r, -small.v);
			}
		}
		else{
			int a, b; cin >> a >> b;
			thing res = root->query(a,a);
			if(res.v >= b) cout << "1\n";
			else cout << "0\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