oj.uz

Submission #396090

# Submission time Handle Problem Language Result Execution time Memory
396090 2021-04-29T12:43:30 Z oolimry Food Court (JOI21_foodcourt) C++17
0 / 100
 1000 ms 37944 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;
#define thing pair<lint, pair<int,int> >
#define v first
#define ll second.first
#define rr second.second
typedef long long lint;
typedef pair<lint, lint> ii;
 
int n, M, Q;
 
inline thing merge(thing a, thing b){
	if(a.v == b.v and a.rr == b.ll - 1) return {a.v, {a.ll, b.rr}};
	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.ll, small.rr, -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 125 ms 9652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 33952 KB Output is correct
2 Correct 587 ms 29104 KB Output is correct
3 Correct 550 ms 37712 KB Output is correct
4 Correct 359 ms 35768 KB Output is correct
5 Correct 373 ms 28276 KB Output is correct
6 Correct 492 ms 37848 KB Output is correct
7 Correct 90 ms 4532 KB Output is correct
8 Correct 89 ms 4536 KB Output is correct
9 Correct 424 ms 37828 KB Output is correct
10 Correct 512 ms 37944 KB Output is correct
11 Correct 594 ms 37828 KB Output is correct
12 Correct 556 ms 37732 KB Output is correct
13 Correct 499 ms 37776 KB Output is correct
14 Correct 603 ms 37788 KB Output is correct
15 Correct 708 ms 37716 KB Output is correct
16 Correct 677 ms 37756 KB Output is correct
17 Correct 666 ms 37716 KB Output is correct
18 Correct 637 ms 37828 KB Output is correct
19 Correct 632 ms 37816 KB Output is correct
20 Correct 630 ms 37844 KB Output is correct
21 Correct 687 ms 37776 KB Output is correct
22 Correct 665 ms 37700 KB Output is correct
23 Correct 625 ms 37624 KB Output is correct
24 Correct 689 ms 37700 KB Output is correct
25 Correct 336 ms 30188 KB Output is correct
26 Correct 369 ms 37400 KB Output is correct
27 Execution timed out 1097 ms 35572 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 78 ms 9568 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 -