oj.uz

Submission #421860

# Submission time Handle Problem Language Result Execution time Memory
421860 2021-06-09T13:04:38 Z shenxy Food Court (JOI21_foodcourt) C++11
7 / 100
 1000 ms 33172 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
#define m (s+e)/2
using namespace std;
typedef pair<int, int> ii;
int N, M, Q, T[250001], L[250001], R[250001], C[250001], ans[250001];
long long K[250001];
void readInt(int &x) {
	x = 0;
	char c = getchar_unlocked();
	while (c < '0' || c > '9') c = getchar_unlocked();
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c - '0');
		c = getchar_unlocked();
	}
}
void readLL(long long &x) {
	x = 0;
	char c = getchar_unlocked();
	while (c < '0' || c > '9') c = getchar_unlocked();
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c - '0');
		c = getchar_unlocked();
	}
}
struct seg {
	int s, e;
	long long lazy, v;
	seg *l, *r;
	seg(int _s, int _e) {
		s = _s, e = _e;
		lazy = 0;
		v = 0;
		if (s != e) {
			l = new seg(s, m);
			r = new seg(m + 1, e);
		}
	}
	void prop() {
		if (lazy) {
			v += lazy;
			if (s != e) {
				l -> lazy += lazy;
				r -> lazy += lazy;
			}
			lazy = 0;
		}
	}
	void update(int a, int b, long long dv) {
		if (s != a || e != b) {
			if (a > m) r -> update(a, b, dv);
			else if (b <= m) l -> update(a, b, dv);
			else l -> update(a, m, dv), r -> update(m + 1, b, dv);
			l -> prop(), r -> prop();
			v = min(l -> v, r -> v);
		} else lazy += dv;
	}
	long long query(int a, int b) {
		prop();
		if (s == a && e == b) return v;
		if (a > m) return r -> query(a, b);
		if (b <= m) return l -> query(a, b);
		return min(l -> query(a, m), r -> query(m + 1, b));
	}
	int descend(int i, long long k) {
		prop();
		if (s == e) return s;
		if (m < i && r -> lazy + r -> v < k) return r -> descend(i, k);
		return l -> descend(i, k);
	}
} *r1;
struct Fenwick {
	long long ft[250001];
	Fenwick() {
		fill_n(ft, 250001, 0);
	}
	void update(int i, long long dv) {
		for (; i <= 250000; i += (i & -i)) ft[i] += dv;
	}
	long long query(int a) {
		long long ans = 0;
		for (; a > 0; a -= (a & -a)) ans += ft[a];
		return ans;
	}
	int descend(int i, long long k) {
		int ans = 0;
		for (int x = 17; x >= 0; --x) {
			if (ans + (1 << x) <= i && ft[ans + (1 << x)] < k) k -= ft[ans + (1 << x)], ans += 1 << x;
		}
		return ans;
	}
} r2;
int main() {
	readInt(N), readInt(M), readInt(Q);
	r1 = new seg(0, Q);
	ii ops[2 * Q];
	int ptr = 0;
	for (int i = 1; i <= Q; ++i) {
		readInt(T[i]);
		if (T[i] == 1) readInt(L[i]), readInt(R[i]), readInt(C[i]), readLL(K[i]);
		else if (T[i] == 2) readInt(L[i]), readInt(R[i]), readLL(K[i]);
		else readInt(L[i]), readLL(K[i]);
		ops[ptr++] = ii(L[i], i);
		if (R[i] != N && T[i] != 3) ops[ptr++] = ii(R[i] + 1, -i);
	}
	sort(ops, ops + ptr);
	for (int h = 0; h < ptr; ++h) {
		int i = ops[h].second;
		if (i < 0 && T[-i] == 1) r1 -> update(-i, Q, -K[-i]), r2.update(-i, -K[-i]);
		else if (i < 0 && T[-i] == 2) r1 -> update(-i, Q, K[-i]);
		else if (T[i] == 3) {
			long long curr = r1 -> query(i, i) - r1 -> query(0, i);
			int l = r2.descend(i, r2.query(i) - curr + K[i]);
			//printf("%d %lld %lld %d\n", i, r2.query(i), curr, l);
			if (l == i) ans[i] = 0;
			else ans[i] = C[l + 1];
		} else if (T[i] == 1) r1 -> update(i, Q, K[i]), r2.update(i, K[i]);
		else r1 -> update(i, Q, -K[i]);
		for (int i = 0; i < Q; ++i) assert(r2.query(i) <= r2.query(i + 1));
	}
	for (int i = 1; i <= Q; ++i) {
		if (T[i] == 3) printf("%d\n", ans[i]);
	}
	return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2380 KB Output is correct
2 Correct 69 ms 2528 KB Output is correct
3 Correct 32 ms 2380 KB Output is correct
4 Correct 71 ms 2528 KB Output is correct
5 Correct 28 ms 2492 KB Output is correct
6 Correct 32 ms 2488 KB Output is correct
7 Correct 73 ms 2528 KB Output is correct
8 Correct 71 ms 2508 KB Output is correct
9 Correct 71 ms 2628 KB Output is correct
10 Correct 72 ms 2508 KB Output is correct
11 Correct 71 ms 2532 KB Output is correct
12 Correct 71 ms 2508 KB Output is correct
13 Correct 25 ms 2380 KB Output is correct
14 Correct 41 ms 2528 KB Output is correct
15 Correct 33 ms 2448 KB Output is correct
16 Correct 66 ms 2536 KB Output is correct
17 Correct 48 ms 2484 KB Output is correct
18 Correct 72 ms 2628 KB Output is correct
19 Correct 58 ms 2508 KB Output is correct
20 Correct 77 ms 2516 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2380 KB Output is correct
2 Correct 69 ms 2528 KB Output is correct
3 Correct 32 ms 2380 KB Output is correct
4 Correct 71 ms 2528 KB Output is correct
5 Correct 28 ms 2492 KB Output is correct
6 Correct 32 ms 2488 KB Output is correct
7 Correct 73 ms 2528 KB Output is correct
8 Correct 71 ms 2508 KB Output is correct
9 Correct 71 ms 2628 KB Output is correct
10 Correct 72 ms 2508 KB Output is correct
11 Correct 71 ms 2532 KB Output is correct
12 Correct 71 ms 2508 KB Output is correct
13 Correct 25 ms 2380 KB Output is correct
14 Correct 41 ms 2528 KB Output is correct
15 Correct 33 ms 2448 KB Output is correct
16 Correct 66 ms 2536 KB Output is correct
17 Correct 48 ms 2484 KB Output is correct
18 Correct 72 ms 2628 KB Output is correct
19 Correct 58 ms 2508 KB Output is correct
20 Correct 77 ms 2516 KB Output is correct
21 Correct 62 ms 2508 KB Output is correct
22 Correct 69 ms 2528 KB Output is correct
23 Correct 62 ms 2508 KB Output is correct
24 Correct 71 ms 2528 KB Output is correct
25 Correct 30 ms 2480 KB Output is correct
26 Correct 38 ms 2484 KB Output is correct
27 Correct 72 ms 2516 KB Output is correct
28 Correct 71 ms 2508 KB Output is correct
29 Correct 72 ms 2508 KB Output is correct
30 Correct 72 ms 2524 KB Output is correct
31 Correct 71 ms 2528 KB Output is correct
32 Correct 72 ms 2516 KB Output is correct
33 Correct 32 ms 2500 KB Output is correct
34 Correct 41 ms 2524 KB Output is correct
35 Correct 65 ms 2484 KB Output is correct
36 Correct 68 ms 2532 KB Output is correct
37 Correct 33 ms 2448 KB Output is correct
38 Correct 74 ms 2508 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 11288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 33172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2380 KB Output is correct
2 Correct 69 ms 2528 KB Output is correct
3 Correct 32 ms 2380 KB Output is correct
4 Correct 71 ms 2528 KB Output is correct
5 Correct 28 ms 2492 KB Output is correct
6 Correct 32 ms 2488 KB Output is correct
7 Correct 73 ms 2528 KB Output is correct
8 Correct 71 ms 2508 KB Output is correct
9 Correct 71 ms 2628 KB Output is correct
10 Correct 72 ms 2508 KB Output is correct
11 Correct 71 ms 2532 KB Output is correct
12 Correct 71 ms 2508 KB Output is correct
13 Correct 25 ms 2380 KB Output is correct
14 Correct 41 ms 2528 KB Output is correct
15 Correct 33 ms 2448 KB Output is correct
16 Correct 66 ms 2536 KB Output is correct
17 Correct 48 ms 2484 KB Output is correct
18 Correct 72 ms 2628 KB Output is correct
19 Correct 58 ms 2508 KB Output is correct
20 Correct 77 ms 2516 KB Output is correct
21 Execution timed out 1089 ms 11288 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 10280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2380 KB Output is correct
2 Correct 69 ms 2528 KB Output is correct
3 Correct 32 ms 2380 KB Output is correct
4 Correct 71 ms 2528 KB Output is correct
5 Correct 28 ms 2492 KB Output is correct
6 Correct 32 ms 2488 KB Output is correct
7 Correct 73 ms 2528 KB Output is correct
8 Correct 71 ms 2508 KB Output is correct
9 Correct 71 ms 2628 KB Output is correct
10 Correct 72 ms 2508 KB Output is correct
11 Correct 71 ms 2532 KB Output is correct
12 Correct 71 ms 2508 KB Output is correct
13 Correct 25 ms 2380 KB Output is correct
14 Correct 41 ms 2528 KB Output is correct
15 Correct 33 ms 2448 KB Output is correct
16 Correct 66 ms 2536 KB Output is correct
17 Correct 48 ms 2484 KB Output is correct
18 Correct 72 ms 2628 KB Output is correct
19 Correct 58 ms 2508 KB Output is correct
20 Correct 77 ms 2516 KB Output is correct
21 Correct 62 ms 2508 KB Output is correct
22 Correct 69 ms 2528 KB Output is correct
23 Correct 62 ms 2508 KB Output is correct
24 Correct 71 ms 2528 KB Output is correct
25 Correct 30 ms 2480 KB Output is correct
26 Correct 38 ms 2484 KB Output is correct
27 Correct 72 ms 2516 KB Output is correct
28 Correct 71 ms 2508 KB Output is correct
29 Correct 72 ms 2508 KB Output is correct
30 Correct 72 ms 2524 KB Output is correct
31 Correct 71 ms 2528 KB Output is correct
32 Correct 72 ms 2516 KB Output is correct
33 Correct 32 ms 2500 KB Output is correct
34 Correct 41 ms 2524 KB Output is correct
35 Correct 65 ms 2484 KB Output is correct
36 Correct 68 ms 2532 KB Output is correct
37 Correct 33 ms 2448 KB Output is correct
38 Correct 74 ms 2508 KB Output is correct
39 Execution timed out 1089 ms 11288 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2380 KB Output is correct
2 Correct 69 ms 2528 KB Output is correct
3 Correct 32 ms 2380 KB Output is correct
4 Correct 71 ms 2528 KB Output is correct
5 Correct 28 ms 2492 KB Output is correct
6 Correct 32 ms 2488 KB Output is correct
7 Correct 73 ms 2528 KB Output is correct
8 Correct 71 ms 2508 KB Output is correct
9 Correct 71 ms 2628 KB Output is correct
10 Correct 72 ms 2508 KB Output is correct
11 Correct 71 ms 2532 KB Output is correct
12 Correct 71 ms 2508 KB Output is correct
13 Correct 25 ms 2380 KB Output is correct
14 Correct 41 ms 2528 KB Output is correct
15 Correct 33 ms 2448 KB Output is correct
16 Correct 66 ms 2536 KB Output is correct
17 Correct 48 ms 2484 KB Output is correct
18 Correct 72 ms 2628 KB Output is correct
19 Correct 58 ms 2508 KB Output is correct
20 Correct 77 ms 2516 KB Output is correct
21 Correct 62 ms 2508 KB Output is correct
22 Correct 69 ms 2528 KB Output is correct
23 Correct 62 ms 2508 KB Output is correct
24 Correct 71 ms 2528 KB Output is correct
25 Correct 30 ms 2480 KB Output is correct
26 Correct 38 ms 2484 KB Output is correct
27 Correct 72 ms 2516 KB Output is correct
28 Correct 71 ms 2508 KB Output is correct
29 Correct 72 ms 2508 KB Output is correct
30 Correct 72 ms 2524 KB Output is correct
31 Correct 71 ms 2528 KB Output is correct
32 Correct 72 ms 2516 KB Output is correct
33 Correct 32 ms 2500 KB Output is correct
34 Correct 41 ms 2524 KB Output is correct
35 Correct 65 ms 2484 KB Output is correct
36 Correct 68 ms 2532 KB Output is correct
37 Correct 33 ms 2448 KB Output is correct
38 Correct 74 ms 2508 KB Output is correct
39 Execution timed out 1089 ms 11288 KB Time limit exceeded
40 Halted 0 ms 0 KB -