oj.uz

Submission #396011

# Submission time Handle Problem Language Result Execution time Memory
396011 2021-04-29T11:08:43 Z oolimry Food Court (JOI21_foodcourt) C++17
0 / 100
 1000 ms 45804 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; };
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;
}

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);
		}
	}
	
	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{
			lint 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 452 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 452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 39820 KB Output is correct
2 Correct 551 ms 35212 KB Output is correct
3 Correct 565 ms 45524 KB Output is correct
4 Correct 387 ms 43608 KB Output is correct
5 Correct 370 ms 34244 KB Output is correct
6 Correct 549 ms 45804 KB Output is correct
7 Correct 101 ms 4544 KB Output is correct
8 Correct 89 ms 4748 KB Output is correct
9 Correct 457 ms 45736 KB Output is correct
10 Correct 441 ms 45720 KB Output is correct
11 Correct 673 ms 45596 KB Output is correct
12 Correct 571 ms 45604 KB Output is correct
13 Correct 530 ms 45548 KB Output is correct
14 Correct 621 ms 45596 KB Output is correct
15 Correct 762 ms 45740 KB Output is correct
16 Correct 709 ms 45568 KB Output is correct
17 Correct 702 ms 45536 KB Output is correct
18 Correct 644 ms 45536 KB Output is correct
19 Correct 702 ms 45532 KB Output is correct
20 Correct 655 ms 45656 KB Output is correct
21 Correct 729 ms 45720 KB Output is correct
22 Correct 692 ms 45644 KB Output is correct
23 Correct 625 ms 45516 KB Output is correct
24 Correct 682 ms 45528 KB Output is correct
25 Correct 352 ms 36120 KB Output is correct
26 Correct 359 ms 45188 KB Output is correct
27 Execution timed out 1098 ms 43420 KB Time limit exceeded

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 10152 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 452 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 452 KB Output isn't correct
2 Halted 0 ms 0 KB -