oj.uz

Submission #396177

# Submission time Handle Problem Language Result Execution time Memory
396177 2021-04-29T14:08:21 Z oolimry Food Court (JOI21_foodcourt) C++17
0 / 100
 1000 ms 39796 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(s != e and lazy != 0){
			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";
		}
	}
	show(cnt);
}

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 35576 KB Output is correct
2 Correct 565 ms 30864 KB Output is correct
3 Correct 564 ms 39540 KB Output is correct
4 Correct 399 ms 39232 KB Output is correct
5 Correct 370 ms 29728 KB Output is correct
6 Correct 535 ms 39796 KB Output is correct
7 Correct 81 ms 452 KB Output is correct
8 Correct 84 ms 452 KB Output is correct
9 Correct 434 ms 39668 KB Output is correct
10 Correct 443 ms 39744 KB Output is correct
11 Correct 575 ms 39512 KB Output is correct
12 Correct 541 ms 39644 KB Output is correct
13 Correct 555 ms 39628 KB Output is correct
14 Correct 612 ms 39564 KB Output is correct
15 Correct 705 ms 39492 KB Output is correct
16 Correct 768 ms 39624 KB Output is correct
17 Correct 713 ms 39480 KB Output is correct
18 Correct 614 ms 39468 KB Output is correct
19 Correct 705 ms 39684 KB Output is correct
20 Correct 635 ms 39520 KB Output is correct
21 Correct 704 ms 39628 KB Output is correct
22 Correct 680 ms 39492 KB Output is correct
23 Correct 604 ms 39620 KB Output is correct
24 Correct 677 ms 39476 KB Output is correct
25 Correct 337 ms 30608 KB Output is correct
26 Correct 342 ms 39572 KB Output is correct
27 Execution timed out 1100 ms 39492 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 79 ms 10116 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 -