Submission #396037

#	Time	Username	Problem	Language	Result	Execution time	Memory
396037		oolimry	Food Court (JOI21_foodcourt)	C++17	0 / 100	1 ms	332 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;

const lint inf = 1234567890123456;
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;
}

const int B = 2;
const int N = 1 << B;
thing tree[2*N];
lint lazy[2*N];

inline void apply(int u, lint L){
	tree[u].v += L;
	lazy[u] += L;
}
inline void push(int leaf){
	leaf += N;
	int u = 0;
	for(int i = B;i >= 1;i--){
		u <<= 1;
		if(leaf & (1<<i)) u |= 1;
		
		apply(u<<1, lazy[u]);
		apply(u<<1|1, lazy[u]);
		lazy[u] = 0;
	}
}
inline void init(){
	for(int i = 0;i < N;i++) tree[i+N] = {0, i, i};
	for(int i = N-1;i > 0;i--) tree[i] = merge(tree[i<<1], tree[i<<1|1]);
}

void update(int l, int r, lint L){
	for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
		if(l&1) apply(l++, L);
		if(r&1) apply(--r, L);
	}
}

thing query(int l, int r){
	push(l), push(r);
	thing L = {inf,0,0}, R = {inf,0,0};
	
	for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
		if(l&1) L = merge(L, tree[l++]);
		if(r&1) R = merge(tree[--r], R);
	}
	
	return merge(L,R);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> M >> Q;
	init();
		
	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 = query(1,n);
				if(small.v >= 0) break;
				update(small.l, small.r, -small.v);
			}
		}
		else{
			lint a, b; cin >> a >> b;
			thing res = query(a,a);
			if(res.v >= b) cout << "1\n";
			else cout << "0\n";
		}
		
		//for(int i = 1;i <= n;i++) cout << query(i,i).v <<  " "; cout << endl;
	}
}

• 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