oj.uz

Submission #645396

# Submission time Handle Problem Language Result Execution time Memory
645396 2022-09-27T04:43:25 Z GusterGoose27 Food Court (JOI21_foodcourt) C++11
68 / 100
 1000 ms 293356 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

class ptree {
public:
	int lp, rp;
	ptree *l = nullptr;
	ptree *r = nullptr;
	ll s = 0;
	ptree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp != rp) {
			int mid = (lp+rp)/2;
			l = new ptree(lp, mid);
			r = new ptree(mid+1, rp);
		}
	}
	ptree(ptree *t, int lupd = 0) {
		lp = t->lp;
		rp = t->rp;
		l = t->l;
		r = t->r;
		s = t->s+lupd;
	}
	ptree(ptree *lt, ptree *rt, ll curs) {
		l = lt;
		r = rt;
		lp = l->lp;
		rp = r->rp;
		s = curs;
	}
	ptree *upd(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return this;
		if (lp >= lv && rp <= rv) {
			return new ptree(this, v);
		}
		return new ptree(l->upd(lv, rv, v), r->upd(lv, rv, v), s);
	}
	ll query(int p) {
		if (lp == rp) return s;
		if (p > (lp+rp)/2) return s+r->query(p);
		return s+l->query(p);
	}
};

const int MAX_ALLOC = 524288;
int sz;

class stree {
public:
	pii lz[MAX_ALLOC];
	stree() {
		fill(lz, lz+(int)pow(2, ceil(log2(sz))), pii(0, 0));
	}
	void merge(int cur, pii p) {
		lz[cur].first += p.first;
		lz[cur].second += p.first;
		lz[cur].second = max(lz[cur].second, p.second);
	}
	void prop(int cur) {
		merge(2*cur, lz[cur]);
		merge(2*cur+1, lz[cur]);
		lz[cur] = pii(0, 0);
	}
	void upd(int lv, int rv, int v, int cur = 1, int lp = 0, int rp = sz-1) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			merge(cur, pii(v, 0));
			return;
		}
		prop(cur);
		int mid = (lp+rp)/2;
		upd(lv, rv, v, 2*cur, lp, mid);
		upd(lv, rv, v, 2*cur+1, mid+1, rp);
	}
	ll getv(int p, int cur = 1, int lp = 0, int rp = sz-1) {
		if (lp == rp) return max(lz[cur].first, lz[cur].second);
		prop(cur);
		int mid = (lp+rp)/2;
		if (p <= mid) return getv(p, 2*cur, lp, mid);
		else return getv(p, 2*cur+1, mid+1, rp);
	}
};

const int MAXN = 250000;
int n, m, q;
int upd_id[MAXN];
ptree *trees[MAXN];
stree *net_tree;
int ev_num = 0;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> q;
	ptree *cur_tree = new ptree(0, n-1);
	sz = n;
	stree *net_tree = new stree();
	for (int i = 0; i < q; i++) {
		int t;
		cin >> t;
		if (t == 1) {
			int l, r, c, k; cin >> l >> r >> c >> k;
			l--; r--;
			upd_id[ev_num] = c;
			cur_tree = cur_tree->upd(l, r, k);
			trees[ev_num] = cur_tree;
			net_tree->upd(l, r, k);
			ev_num++;
		}
		if (t == 2) {
			int l, r, k; cin >> l >> r >> k;
			l--; r--;
			net_tree->upd(l, r, -k);
		}
		if (t == 3) {
			int a; ll b; cin >> a >> b; a--;
			ll cur_sz = net_tree->getv(a);
			if (cur_sz < b) {
				cout << "0\n";
				continue;
			}
			ll num_adds = trees[ev_num-1]->query(a);
			ll req_sz = num_adds-cur_sz+b;
			int mn = -1;
			int mx = ev_num-1;
			while (mx > mn+1) {
				int cur = (mn+mx)/2;
				if (trees[cur]->query(a) < req_sz) mn = cur;
				else mx = cur;
			}
			cout << upd_id[mx] << "\n";
		}
	}
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9300 KB Output is correct
2 Correct 8 ms 9512 KB Output is correct
3 Correct 6 ms 9556 KB Output is correct
4 Correct 6 ms 10048 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 4 ms 8532 KB Output is correct
7 Correct 6 ms 9660 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9696 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 4 ms 8660 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 5 ms 9428 KB Output is correct
16 Correct 7 ms 9716 KB Output is correct
17 Correct 5 ms 9428 KB Output is correct
18 Correct 7 ms 9684 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 6 ms 9940 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9300 KB Output is correct
2 Correct 8 ms 9512 KB Output is correct
3 Correct 6 ms 9556 KB Output is correct
4 Correct 6 ms 10048 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 4 ms 8532 KB Output is correct
7 Correct 6 ms 9660 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9696 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 4 ms 8660 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 5 ms 9428 KB Output is correct
16 Correct 7 ms 9716 KB Output is correct
17 Correct 5 ms 9428 KB Output is correct
18 Correct 7 ms 9684 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 6 ms 9940 KB Output is correct
21 Correct 6 ms 9432 KB Output is correct
22 Correct 6 ms 9556 KB Output is correct
23 Correct 6 ms 9812 KB Output is correct
24 Correct 6 ms 10068 KB Output is correct
25 Correct 4 ms 8544 KB Output is correct
26 Correct 5 ms 8532 KB Output is correct
27 Correct 7 ms 9684 KB Output is correct
28 Correct 6 ms 9724 KB Output is correct
29 Correct 6 ms 9684 KB Output is correct
30 Correct 6 ms 9684 KB Output is correct
31 Correct 6 ms 9684 KB Output is correct
32 Correct 7 ms 9684 KB Output is correct
33 Correct 4 ms 8660 KB Output is correct
34 Correct 5 ms 8788 KB Output is correct
35 Correct 6 ms 9556 KB Output is correct
36 Correct 6 ms 9812 KB Output is correct
37 Correct 6 ms 9476 KB Output is correct
38 Correct 6 ms 9940 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 35284 KB Output is correct
2 Correct 97 ms 45900 KB Output is correct
3 Correct 83 ms 37312 KB Output is correct
4 Correct 80 ms 37120 KB Output is correct
5 Correct 100 ms 48684 KB Output is correct
6 Correct 115 ms 48604 KB Output is correct
7 Correct 19 ms 9764 KB Output is correct
8 Correct 19 ms 9928 KB Output is correct
9 Correct 88 ms 37804 KB Output is correct
10 Correct 86 ms 37836 KB Output is correct
11 Correct 83 ms 38068 KB Output is correct
12 Correct 83 ms 38100 KB Output is correct
13 Correct 104 ms 43008 KB Output is correct
14 Correct 105 ms 49152 KB Output is correct
15 Correct 124 ms 63876 KB Output is correct
16 Correct 129 ms 67168 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 786 ms 201176 KB Output is correct
2 Correct 578 ms 161760 KB Output is correct
3 Correct 967 ms 220864 KB Output is correct
4 Correct 825 ms 241940 KB Output is correct
5 Correct 834 ms 237432 KB Output is correct
6 Execution timed out 1085 ms 293356 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9300 KB Output is correct
2 Correct 8 ms 9512 KB Output is correct
3 Correct 6 ms 9556 KB Output is correct
4 Correct 6 ms 10048 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 4 ms 8532 KB Output is correct
7 Correct 6 ms 9660 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9696 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 4 ms 8660 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 5 ms 9428 KB Output is correct
16 Correct 7 ms 9716 KB Output is correct
17 Correct 5 ms 9428 KB Output is correct
18 Correct 7 ms 9684 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 6 ms 9940 KB Output is correct
21 Correct 86 ms 35284 KB Output is correct
22 Correct 97 ms 45900 KB Output is correct
23 Correct 83 ms 37312 KB Output is correct
24 Correct 80 ms 37120 KB Output is correct
25 Correct 100 ms 48684 KB Output is correct
26 Correct 115 ms 48604 KB Output is correct
27 Correct 19 ms 9764 KB Output is correct
28 Correct 19 ms 9928 KB Output is correct
29 Correct 88 ms 37804 KB Output is correct
30 Correct 86 ms 37836 KB Output is correct
31 Correct 83 ms 38068 KB Output is correct
32 Correct 83 ms 38100 KB Output is correct
33 Correct 104 ms 43008 KB Output is correct
34 Correct 105 ms 49152 KB Output is correct
35 Correct 124 ms 63876 KB Output is correct
36 Correct 129 ms 67168 KB Output is correct
37 Correct 142 ms 52044 KB Output is correct
38 Correct 199 ms 66880 KB Output is correct
39 Correct 17 ms 9684 KB Output is correct
40 Correct 20 ms 10352 KB Output is correct
41 Correct 187 ms 64668 KB Output is correct
42 Correct 197 ms 65004 KB Output is correct
43 Correct 164 ms 64588 KB Output is correct
44 Correct 178 ms 64588 KB Output is correct
45 Correct 197 ms 64808 KB Output is correct
46 Correct 159 ms 64748 KB Output is correct
47 Correct 45 ms 16076 KB Output is correct
48 Correct 122 ms 65676 KB Output is correct
49 Correct 105 ms 48460 KB Output is correct
50 Correct 146 ms 58432 KB Output is correct
51 Correct 178 ms 66692 KB Output is correct
52 Correct 161 ms 66580 KB Output is correct
53 Correct 100 ms 54948 KB Output is correct
54 Correct 138 ms 67212 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 71732 KB Output is correct
2 Correct 285 ms 76568 KB Output is correct
3 Correct 301 ms 79376 KB Output is correct
4 Correct 199 ms 61248 KB Output is correct
5 Correct 250 ms 71808 KB Output is correct
6 Correct 298 ms 81668 KB Output is correct
7 Correct 26 ms 10324 KB Output is correct
8 Correct 26 ms 10828 KB Output is correct
9 Correct 64 ms 16700 KB Output is correct
10 Correct 176 ms 66380 KB Output is correct
11 Correct 217 ms 91572 KB Output is correct
12 Correct 218 ms 91232 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9300 KB Output is correct
2 Correct 8 ms 9512 KB Output is correct
3 Correct 6 ms 9556 KB Output is correct
4 Correct 6 ms 10048 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 4 ms 8532 KB Output is correct
7 Correct 6 ms 9660 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9696 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 4 ms 8660 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 5 ms 9428 KB Output is correct
16 Correct 7 ms 9716 KB Output is correct
17 Correct 5 ms 9428 KB Output is correct
18 Correct 7 ms 9684 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 6 ms 9940 KB Output is correct
21 Correct 6 ms 9432 KB Output is correct
22 Correct 6 ms 9556 KB Output is correct
23 Correct 6 ms 9812 KB Output is correct
24 Correct 6 ms 10068 KB Output is correct
25 Correct 4 ms 8544 KB Output is correct
26 Correct 5 ms 8532 KB Output is correct
27 Correct 7 ms 9684 KB Output is correct
28 Correct 6 ms 9724 KB Output is correct
29 Correct 6 ms 9684 KB Output is correct
30 Correct 6 ms 9684 KB Output is correct
31 Correct 6 ms 9684 KB Output is correct
32 Correct 7 ms 9684 KB Output is correct
33 Correct 4 ms 8660 KB Output is correct
34 Correct 5 ms 8788 KB Output is correct
35 Correct 6 ms 9556 KB Output is correct
36 Correct 6 ms 9812 KB Output is correct
37 Correct 6 ms 9476 KB Output is correct
38 Correct 6 ms 9940 KB Output is correct
39 Correct 86 ms 35284 KB Output is correct
40 Correct 97 ms 45900 KB Output is correct
41 Correct 83 ms 37312 KB Output is correct
42 Correct 80 ms 37120 KB Output is correct
43 Correct 100 ms 48684 KB Output is correct
44 Correct 115 ms 48604 KB Output is correct
45 Correct 19 ms 9764 KB Output is correct
46 Correct 19 ms 9928 KB Output is correct
47 Correct 88 ms 37804 KB Output is correct
48 Correct 86 ms 37836 KB Output is correct
49 Correct 83 ms 38068 KB Output is correct
50 Correct 83 ms 38100 KB Output is correct
51 Correct 104 ms 43008 KB Output is correct
52 Correct 105 ms 49152 KB Output is correct
53 Correct 124 ms 63876 KB Output is correct
54 Correct 129 ms 67168 KB Output is correct
55 Correct 142 ms 52044 KB Output is correct
56 Correct 199 ms 66880 KB Output is correct
57 Correct 17 ms 9684 KB Output is correct
58 Correct 20 ms 10352 KB Output is correct
59 Correct 187 ms 64668 KB Output is correct
60 Correct 197 ms 65004 KB Output is correct
61 Correct 164 ms 64588 KB Output is correct
62 Correct 178 ms 64588 KB Output is correct
63 Correct 197 ms 64808 KB Output is correct
64 Correct 159 ms 64748 KB Output is correct
65 Correct 45 ms 16076 KB Output is correct
66 Correct 122 ms 65676 KB Output is correct
67 Correct 105 ms 48460 KB Output is correct
68 Correct 146 ms 58432 KB Output is correct
69 Correct 178 ms 66692 KB Output is correct
70 Correct 161 ms 66580 KB Output is correct
71 Correct 100 ms 54948 KB Output is correct
72 Correct 138 ms 67212 KB Output is correct
73 Correct 273 ms 71732 KB Output is correct
74 Correct 285 ms 76568 KB Output is correct
75 Correct 301 ms 79376 KB Output is correct
76 Correct 199 ms 61248 KB Output is correct
77 Correct 250 ms 71808 KB Output is correct
78 Correct 298 ms 81668 KB Output is correct
79 Correct 26 ms 10324 KB Output is correct
80 Correct 26 ms 10828 KB Output is correct
81 Correct 64 ms 16700 KB Output is correct
82 Correct 176 ms 66380 KB Output is correct
83 Correct 217 ms 91572 KB Output is correct
84 Correct 218 ms 91232 KB Output is correct
85 Correct 141 ms 51640 KB Output is correct
86 Correct 187 ms 58024 KB Output is correct
87 Correct 202 ms 72456 KB Output is correct
88 Correct 248 ms 81356 KB Output is correct
89 Correct 124 ms 46256 KB Output is correct
90 Correct 217 ms 64988 KB Output is correct
91 Correct 130 ms 52644 KB Output is correct
92 Correct 122 ms 50436 KB Output is correct
93 Correct 163 ms 64704 KB Output is correct
94 Correct 201 ms 65128 KB Output is correct
95 Correct 176 ms 62932 KB Output is correct
96 Correct 167 ms 65228 KB Output is correct
97 Correct 162 ms 64868 KB Output is correct
98 Correct 136 ms 54604 KB Output is correct
99 Correct 51 ms 15948 KB Output is correct
100 Correct 110 ms 56564 KB Output is correct
101 Correct 131 ms 65384 KB Output is correct
102 Correct 155 ms 64392 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9300 KB Output is correct
2 Correct 8 ms 9512 KB Output is correct
3 Correct 6 ms 9556 KB Output is correct
4 Correct 6 ms 10048 KB Output is correct
5 Correct 4 ms 8532 KB Output is correct
6 Correct 4 ms 8532 KB Output is correct
7 Correct 6 ms 9660 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 6 ms 9696 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9684 KB Output is correct
13 Correct 4 ms 8660 KB Output is correct
14 Correct 5 ms 8788 KB Output is correct
15 Correct 5 ms 9428 KB Output is correct
16 Correct 7 ms 9716 KB Output is correct
17 Correct 5 ms 9428 KB Output is correct
18 Correct 7 ms 9684 KB Output is correct
19 Correct 6 ms 9684 KB Output is correct
20 Correct 6 ms 9940 KB Output is correct
21 Correct 6 ms 9432 KB Output is correct
22 Correct 6 ms 9556 KB Output is correct
23 Correct 6 ms 9812 KB Output is correct
24 Correct 6 ms 10068 KB Output is correct
25 Correct 4 ms 8544 KB Output is correct
26 Correct 5 ms 8532 KB Output is correct
27 Correct 7 ms 9684 KB Output is correct
28 Correct 6 ms 9724 KB Output is correct
29 Correct 6 ms 9684 KB Output is correct
30 Correct 6 ms 9684 KB Output is correct
31 Correct 6 ms 9684 KB Output is correct
32 Correct 7 ms 9684 KB Output is correct
33 Correct 4 ms 8660 KB Output is correct
34 Correct 5 ms 8788 KB Output is correct
35 Correct 6 ms 9556 KB Output is correct
36 Correct 6 ms 9812 KB Output is correct
37 Correct 6 ms 9476 KB Output is correct
38 Correct 6 ms 9940 KB Output is correct
39 Correct 86 ms 35284 KB Output is correct
40 Correct 97 ms 45900 KB Output is correct
41 Correct 83 ms 37312 KB Output is correct
42 Correct 80 ms 37120 KB Output is correct
43 Correct 100 ms 48684 KB Output is correct
44 Correct 115 ms 48604 KB Output is correct
45 Correct 19 ms 9764 KB Output is correct
46 Correct 19 ms 9928 KB Output is correct
47 Correct 88 ms 37804 KB Output is correct
48 Correct 86 ms 37836 KB Output is correct
49 Correct 83 ms 38068 KB Output is correct
50 Correct 83 ms 38100 KB Output is correct
51 Correct 104 ms 43008 KB Output is correct
52 Correct 105 ms 49152 KB Output is correct
53 Correct 124 ms 63876 KB Output is correct
54 Correct 129 ms 67168 KB Output is correct
55 Correct 786 ms 201176 KB Output is correct
56 Correct 578 ms 161760 KB Output is correct
57 Correct 967 ms 220864 KB Output is correct
58 Correct 825 ms 241940 KB Output is correct
59 Correct 834 ms 237432 KB Output is correct
60 Execution timed out 1085 ms 293356 KB Time limit exceeded
61 Halted 0 ms 0 KB -