Submission #396184

#	Time	Username	Problem	Language	Result	Execution time	Memory
396184		oolimry	Food Court (JOI21_foodcourt)	C++17	0 / 100	1097 ms	43700 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{ lint v, l, r; };
inline thing merge(thing a, thing b){
	if(a.v == b.v and a.r == b.l - 1) return {a.v, a.l, b.r};
	else if(a.v > b.v) return b;
	else return a;
}

int cnt = 0;
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,e}; lazy = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	inline void apply(lint L){
		val.v += L;
		lazy += L;
	}
	inline void push(){
		if(lazy != 0 and 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(){ return val; }
} *root;

const int N = (1<<18);
lint tree[2*N];
void update(int l, int r, lint k){
	root->update(l,r,k);
	for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
		if(l&1) tree[l++] += k;
		if(r&1) tree[--r] += k;
	}
}
lint query(int i){
	lint res = 0;
	for(i += N;i;i >>= 1) res += tree[i];
	return res;
}


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;
			update(l,r,k);
		}
		else if(t == 2){
			int l, r, k; cin >> l >> r >> k;
			update(l,r,-k);
			
			while(true){
				thing small = root->query();
				if(small.v >= 0) break;
				update(small.l, small.r, -small.v);
			}
		}
		else{
			lint a, b; cin >> a >> b;
			if(query(a) >= 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