oj.uz

Submission #396192

# Submission time Handle Problem Language Result Execution time Memory
396192 2021-04-29T14:18:24 Z oolimry Food Court (JOI21_foodcourt) C++17
0 / 100
 1000 ms 43604 KB 
#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){
		if(S <= s and e <= E){
			apply(L); return;
		}
		push();
		if(S <= m) l->update(S, E, L);
		if(E > m) r->update(S, 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 11680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 39124 KB Output is correct
2 Correct 574 ms 33856 KB Output is correct
3 Correct 541 ms 43460 KB Output is correct
4 Correct 399 ms 43184 KB Output is correct
5 Correct 352 ms 32620 KB Output is correct
6 Correct 499 ms 43476 KB Output is correct
7 Correct 85 ms 484 KB Output is correct
8 Correct 88 ms 520 KB Output is correct
9 Correct 398 ms 43564 KB Output is correct
10 Correct 400 ms 43592 KB Output is correct
11 Correct 592 ms 43496 KB Output is correct
12 Correct 528 ms 43488 KB Output is correct
13 Correct 501 ms 43488 KB Output is correct
14 Correct 603 ms 43444 KB Output is correct
15 Correct 751 ms 43456 KB Output is correct
16 Correct 684 ms 43480 KB Output is correct
17 Correct 684 ms 43456 KB Output is correct
18 Correct 603 ms 43460 KB Output is correct
19 Correct 627 ms 43604 KB Output is correct
20 Correct 612 ms 43464 KB Output is correct
21 Correct 693 ms 43520 KB Output is correct
22 Correct 684 ms 43480 KB Output is correct
23 Correct 605 ms 43416 KB Output is correct
24 Correct 645 ms 43432 KB Output is correct
25 Correct 286 ms 30804 KB Output is correct
26 Correct 298 ms 39716 KB Output is correct
27 Execution timed out 1058 ms 43380 KB Time limit exceeded

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 11176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -