oj.uz

Submission #396013

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

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(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 460 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 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 35472 KB Output is correct
2 Correct 530 ms 30788 KB Output is correct
3 Correct 559 ms 39492 KB Output is correct
4 Correct 395 ms 39364 KB Output is correct
5 Correct 360 ms 29728 KB Output is correct
6 Correct 512 ms 39704 KB Output is correct
7 Correct 85 ms 452 KB Output is correct
8 Correct 82 ms 452 KB Output is correct
9 Correct 437 ms 39572 KB Output is correct
10 Correct 442 ms 39616 KB Output is correct
11 Correct 606 ms 39592 KB Output is correct
12 Correct 557 ms 39768 KB Output is correct
13 Correct 527 ms 39712 KB Output is correct
14 Correct 620 ms 39496 KB Output is correct
15 Correct 697 ms 39560 KB Output is correct
16 Correct 699 ms 39596 KB Output is correct
17 Correct 682 ms 39748 KB Output is correct
18 Correct 617 ms 39572 KB Output is correct
19 Correct 695 ms 39616 KB Output is correct
20 Correct 648 ms 39624 KB Output is correct
21 Correct 716 ms 39696 KB Output is correct
22 Correct 683 ms 39640 KB Output is correct
23 Correct 602 ms 39656 KB Output is correct
24 Correct 653 ms 39568 KB Output is correct
25 Correct 344 ms 30660 KB Output is correct
26 Correct 344 ms 39580 KB Output is correct
27 Execution timed out 1094 ms 39448 KB Time limit exceeded

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

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