oj.uz

Submission #331846

# Submission time Handle Problem Language Result Execution time Memory
331846 2020-11-30T12:18:46 Z keko37 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 2301 ms 95748 KB 
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1000005;
const int INF = 1000000007;

int n, m, ofs = 1;
int w[MAXN], lef[MAXN], rig[MAXN], mood[MAXN], ans[MAXN];
int t[MAXN * 4], mx[MAXN * 4];
vector <int> v[MAXN], r;

void build () {
    for (int i = 0; i < 2 * ofs; i++) mx[i] = -INF;
    for (int i = 0; i < n; i++) mx[i + ofs] = w[i];
    for (int i = ofs - 1; i > 0; i--) {
        mx[i] = max(mx[2 * i], mx[2 * i + 1]);
    }
}

void update (int pos, int val) {
    pos += ofs;
    t[pos] = val;
    pos /= 2;
    while (pos > 0) {
        t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
        pos /= 2;
    }
}

int upit (int x, int from, int to, int lo, int hi) {
    if (from <= lo && hi <= to) return t[x];
    if (to < lo || hi < from) return -INF;
    return max(upit(2 * x, from, to, lo, (lo + hi) / 2), upit(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi));
}

int upit_mx (int x, int from, int to, int lo, int hi) {
    if (from <= lo && hi <= to) return mx[x];
    if (to < lo || hi < from) return -INF;
    return max(upit_mx(2 * x, from, to, lo, (lo + hi) / 2), upit_mx(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi));
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    while (ofs < n) ofs *= 2;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
    }
    build();
    for (int i = 0; i < m; i++) {
        cin >> lef[i] >> rig[i] >> mood[i];
        lef[i]--; rig[i]--;
        v[lef[i]].push_back(i);
    }
    for (int i = n - 1; i >= 0; i--) {
        int val = -INF;
        while (!r.empty() && w[i] > w[-r.back()]) {
            val = max(val, w[-r.back()]);
            update(-r.back(), -INF);
            r.pop_back();
        }
        update(i, w[i] + val);
        r.push_back(-i);

        for (int q : v[i]) {
            int pos = -*lower_bound(r.begin(), r.end(), -rig[q]);
            ans[q] = -INF;
            if (i < pos) ans[q] = max(ans[q], upit(1, i, pos - 1, 0, ofs - 1));
            if (pos < rig[q]) ans[q] = max(ans[q], w[pos] + upit_mx(1, pos + 1, rig[q], 0, ofs - 1));
        }
    }
    for (int i = 0; i < m; i++) {
        cout << (ans[i] <= mood[i]) << '\n';
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23916 KB Output is correct
2 Correct 15 ms 23916 KB Output is correct
3 Correct 16 ms 23916 KB Output is correct
4 Correct 16 ms 23916 KB Output is correct
5 Correct 16 ms 23916 KB Output is correct
6 Correct 15 ms 23916 KB Output is correct
7 Correct 16 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 16 ms 23916 KB Output is correct
10 Correct 17 ms 24060 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23916 KB Output is correct
2 Correct 15 ms 23916 KB Output is correct
3 Correct 16 ms 23916 KB Output is correct
4 Correct 16 ms 23916 KB Output is correct
5 Correct 16 ms 23916 KB Output is correct
6 Correct 15 ms 23916 KB Output is correct
7 Correct 16 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 16 ms 23916 KB Output is correct
10 Correct 17 ms 24060 KB Output is correct
11 Correct 19 ms 24044 KB Output is correct
12 Correct 19 ms 24172 KB Output is correct
13 Correct 21 ms 24300 KB Output is correct
14 Correct 22 ms 24300 KB Output is correct
15 Correct 21 ms 24300 KB Output is correct
16 Correct 19 ms 24300 KB Output is correct
17 Correct 23 ms 24300 KB Output is correct
18 Correct 19 ms 24300 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2253 ms 83396 KB Output is correct
2 Correct 2301 ms 83728 KB Output is correct
3 Correct 2224 ms 83708 KB Output is correct
4 Correct 2241 ms 83952 KB Output is correct
5 Correct 2139 ms 90824 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 31852 KB Output is correct
2 Correct 155 ms 30828 KB Output is correct
3 Correct 152 ms 32248 KB Output is correct
4 Correct 152 ms 32304 KB Output is correct
5 Correct 152 ms 32364 KB Output is correct
6 Correct 118 ms 30820 KB Output is correct
7 Correct 118 ms 30820 KB Output is correct
8 Correct 154 ms 31080 KB Output is correct
9 Correct 72 ms 27496 KB Output is correct
10 Correct 162 ms 31080 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23916 KB Output is correct
2 Correct 15 ms 23916 KB Output is correct
3 Correct 16 ms 23916 KB Output is correct
4 Correct 16 ms 23916 KB Output is correct
5 Correct 16 ms 23916 KB Output is correct
6 Correct 15 ms 23916 KB Output is correct
7 Correct 16 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 16 ms 23916 KB Output is correct
10 Correct 17 ms 24060 KB Output is correct
11 Correct 19 ms 24044 KB Output is correct
12 Correct 19 ms 24172 KB Output is correct
13 Correct 21 ms 24300 KB Output is correct
14 Correct 22 ms 24300 KB Output is correct
15 Correct 21 ms 24300 KB Output is correct
16 Correct 19 ms 24300 KB Output is correct
17 Correct 23 ms 24300 KB Output is correct
18 Correct 19 ms 24300 KB Output is correct
19 Correct 392 ms 42348 KB Output is correct
20 Correct 391 ms 42476 KB Output is correct
21 Correct 339 ms 39916 KB Output is correct
22 Correct 356 ms 40044 KB Output is correct
23 Correct 347 ms 40044 KB Output is correct
24 Correct 266 ms 40544 KB Output is correct
25 Correct 266 ms 40684 KB Output is correct
26 Correct 326 ms 41824 KB Output is correct
27 Correct 312 ms 41568 KB Output is correct
28 Correct 335 ms 42200 KB Output is correct
29 Correct 341 ms 43240 KB Output is correct
30 Correct 354 ms 43632 KB Output is correct
31 Correct 365 ms 43232 KB Output is correct
32 Correct 359 ms 43232 KB Output is correct
33 Correct 354 ms 43360 KB Output is correct
34 Correct 251 ms 40032 KB Output is correct
35 Correct 248 ms 40160 KB Output is correct
36 Correct 247 ms 40032 KB Output is correct
37 Correct 244 ms 39904 KB Output is correct
38 Correct 251 ms 40288 KB Output is correct
39 Correct 301 ms 40168 KB Output is correct
40 Correct 226 ms 37220 KB Output is correct
41 Correct 325 ms 39656 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23916 KB Output is correct
2 Correct 15 ms 23916 KB Output is correct
3 Correct 16 ms 23916 KB Output is correct
4 Correct 16 ms 23916 KB Output is correct
5 Correct 16 ms 23916 KB Output is correct
6 Correct 15 ms 23916 KB Output is correct
7 Correct 16 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 16 ms 23916 KB Output is correct
10 Correct 17 ms 24060 KB Output is correct
11 Correct 19 ms 24044 KB Output is correct
12 Correct 19 ms 24172 KB Output is correct
13 Correct 21 ms 24300 KB Output is correct
14 Correct 22 ms 24300 KB Output is correct
15 Correct 21 ms 24300 KB Output is correct
16 Correct 19 ms 24300 KB Output is correct
17 Correct 23 ms 24300 KB Output is correct
18 Correct 19 ms 24300 KB Output is correct
19 Correct 2253 ms 83396 KB Output is correct
20 Correct 2301 ms 83728 KB Output is correct
21 Correct 2224 ms 83708 KB Output is correct
22 Correct 2241 ms 83952 KB Output is correct
23 Correct 2139 ms 90824 KB Output is correct
24 Correct 182 ms 31852 KB Output is correct
25 Correct 155 ms 30828 KB Output is correct
26 Correct 152 ms 32248 KB Output is correct
27 Correct 152 ms 32304 KB Output is correct
28 Correct 152 ms 32364 KB Output is correct
29 Correct 118 ms 30820 KB Output is correct
30 Correct 118 ms 30820 KB Output is correct
31 Correct 154 ms 31080 KB Output is correct
32 Correct 72 ms 27496 KB Output is correct
33 Correct 162 ms 31080 KB Output is correct
34 Correct 392 ms 42348 KB Output is correct
35 Correct 391 ms 42476 KB Output is correct
36 Correct 339 ms 39916 KB Output is correct
37 Correct 356 ms 40044 KB Output is correct
38 Correct 347 ms 40044 KB Output is correct
39 Correct 266 ms 40544 KB Output is correct
40 Correct 266 ms 40684 KB Output is correct
41 Correct 326 ms 41824 KB Output is correct
42 Correct 312 ms 41568 KB Output is correct
43 Correct 335 ms 42200 KB Output is correct
44 Correct 341 ms 43240 KB Output is correct
45 Correct 354 ms 43632 KB Output is correct
46 Correct 365 ms 43232 KB Output is correct
47 Correct 359 ms 43232 KB Output is correct
48 Correct 354 ms 43360 KB Output is correct
49 Correct 251 ms 40032 KB Output is correct
50 Correct 248 ms 40160 KB Output is correct
51 Correct 247 ms 40032 KB Output is correct
52 Correct 244 ms 39904 KB Output is correct
53 Correct 251 ms 40288 KB Output is correct
54 Correct 301 ms 40168 KB Output is correct
55 Correct 226 ms 37220 KB Output is correct
56 Correct 325 ms 39656 KB Output is correct
57 Correct 2240 ms 85828 KB Output is correct
58 Correct 2198 ms 86096 KB Output is correct
59 Correct 2055 ms 80660 KB Output is correct
60 Correct 2102 ms 80640 KB Output is correct
61 Correct 2033 ms 80572 KB Output is correct
62 Correct 2159 ms 80416 KB Output is correct
63 Correct 1389 ms 75600 KB Output is correct
64 Correct 1430 ms 75960 KB Output is correct
65 Correct 1921 ms 83412 KB Output is correct
66 Correct 1947 ms 83384 KB Output is correct
67 Correct 1939 ms 84236 KB Output is correct
68 Correct 2079 ms 90172 KB Output is correct
69 Correct 2097 ms 90432 KB Output is correct
70 Correct 2037 ms 88788 KB Output is correct
71 Correct 2061 ms 95748 KB Output is correct
72 Correct 2049 ms 89120 KB Output is correct
73 Correct 1251 ms 75548 KB Output is correct
74 Correct 1310 ms 75624 KB Output is correct
75 Correct 1279 ms 75520 KB Output is correct
76 Correct 1251 ms 75476 KB Output is correct
77 Correct 1263 ms 75620 KB Output is correct
78 Correct 1783 ms 80840 KB Output is correct
79 Correct 1301 ms 80984 KB Output is correct
80 Correct 1888 ms 81700 KB Output is correct