oj.uz

Submission #424054

# Submission time Handle Problem Language Result Execution time Memory
424054 2021-06-11T15:57:39 Z doowey Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 2052 ms 97592 KB 
#include <bits/stdc++.h>

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e6 + 10;

int val[N * 4 + 512];
int X[N];

void update(int node, int cl, int cr, int id, int v){
    if(cl == cr){
        val[node] = max(val[node], v);
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= id)
        update(node * 2, cl, mid, id, v);
    else
        update(node * 2 + 1, mid + 1, cr, id, v);
    val[node]=max(val[node*2],val[node*2+1]);
}

int get(int node, int cl, int cr, int tl, int tr){
    if(cr < tl || cl > tr) return 0;
    if(cl >= tl && cr <= tr){
        return val[node];
    }
    int mid = (cl + cr) / 2;
    return max(get(node * 2, cl, mid, tl, tr),get(node*2+1, mid + 1, cr, tl, tr));
}

vector<pii> Q[N];
int idx[N];
bool res[N];

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++ ){
        cin >> X[i];
    }

    int li, ri;
    int lq;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> li >> ri >> lq;
        idx[iq] = lq;
        Q[li].push_back(mp(ri, iq));
    }
    vector<int> ids;

    for(int i = n; i >= 1; i -- ){

        while(!ids.empty() && X[i] > X[ids.back()]){
            update(1, 1, n, ids.back(), X[i] + X[ids.back()]);
            ids.pop_back();
        }
        ids.push_back(i);

        for(auto x : Q[i]){
            res[x.se] = (get(1, 1, n, i, x.fi) <= idx[x.se]);
        }
    }
    for(int iq = 1; iq <= q; iq ++ ){
        cout << res[iq] << "\n";
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23800 KB Output is correct
2 Correct 16 ms 23756 KB Output is correct
3 Correct 14 ms 23824 KB Output is correct
4 Correct 14 ms 23756 KB Output is correct
5 Correct 15 ms 23760 KB Output is correct
6 Correct 19 ms 23756 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct
8 Correct 15 ms 23756 KB Output is correct
9 Correct 18 ms 23756 KB Output is correct
10 Correct 17 ms 23788 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23800 KB Output is correct
2 Correct 16 ms 23756 KB Output is correct
3 Correct 14 ms 23824 KB Output is correct
4 Correct 14 ms 23756 KB Output is correct
5 Correct 15 ms 23760 KB Output is correct
6 Correct 19 ms 23756 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct
8 Correct 15 ms 23756 KB Output is correct
9 Correct 18 ms 23756 KB Output is correct
10 Correct 17 ms 23788 KB Output is correct
11 Correct 19 ms 23864 KB Output is correct
12 Correct 19 ms 23884 KB Output is correct
13 Correct 18 ms 23884 KB Output is correct
14 Correct 23 ms 23916 KB Output is correct
15 Correct 23 ms 24020 KB Output is correct
16 Correct 22 ms 24016 KB Output is correct
17 Correct 18 ms 23980 KB Output is correct
18 Correct 19 ms 23948 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2011 ms 81740 KB Output is correct
2 Correct 2052 ms 95532 KB Output is correct
3 Correct 2020 ms 95452 KB Output is correct
4 Correct 1936 ms 95552 KB Output is correct
5 Correct 1626 ms 91436 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 28020 KB Output is correct
2 Correct 132 ms 27432 KB Output is correct
3 Correct 117 ms 27248 KB Output is correct
4 Correct 118 ms 27452 KB Output is correct
5 Correct 138 ms 27500 KB Output is correct
6 Correct 97 ms 26576 KB Output is correct
7 Correct 104 ms 26584 KB Output is correct
8 Correct 119 ms 27540 KB Output is correct
9 Correct 60 ms 25500 KB Output is correct
10 Correct 121 ms 27536 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23800 KB Output is correct
2 Correct 16 ms 23756 KB Output is correct
3 Correct 14 ms 23824 KB Output is correct
4 Correct 14 ms 23756 KB Output is correct
5 Correct 15 ms 23760 KB Output is correct
6 Correct 19 ms 23756 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct
8 Correct 15 ms 23756 KB Output is correct
9 Correct 18 ms 23756 KB Output is correct
10 Correct 17 ms 23788 KB Output is correct
11 Correct 19 ms 23864 KB Output is correct
12 Correct 19 ms 23884 KB Output is correct
13 Correct 18 ms 23884 KB Output is correct
14 Correct 23 ms 23916 KB Output is correct
15 Correct 23 ms 24020 KB Output is correct
16 Correct 22 ms 24016 KB Output is correct
17 Correct 18 ms 23980 KB Output is correct
18 Correct 19 ms 23948 KB Output is correct
19 Correct 423 ms 32192 KB Output is correct
20 Correct 324 ms 32148 KB Output is correct
21 Correct 295 ms 30772 KB Output is correct
22 Correct 282 ms 30848 KB Output is correct
23 Correct 332 ms 30732 KB Output is correct
24 Correct 231 ms 29604 KB Output is correct
25 Correct 220 ms 29520 KB Output is correct
26 Correct 302 ms 30176 KB Output is correct
27 Correct 297 ms 30128 KB Output is correct
28 Correct 324 ms 30276 KB Output is correct
29 Correct 325 ms 31092 KB Output is correct
30 Correct 284 ms 31036 KB Output is correct
31 Correct 324 ms 31028 KB Output is correct
32 Correct 293 ms 30996 KB Output is correct
33 Correct 286 ms 30956 KB Output is correct
34 Correct 233 ms 29192 KB Output is correct
35 Correct 226 ms 29104 KB Output is correct
36 Correct 218 ms 29120 KB Output is correct
37 Correct 200 ms 29072 KB Output is correct
38 Correct 216 ms 29172 KB Output is correct
39 Correct 253 ms 30468 KB Output is correct
40 Correct 178 ms 29624 KB Output is correct
41 Correct 256 ms 31216 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23800 KB Output is correct
2 Correct 16 ms 23756 KB Output is correct
3 Correct 14 ms 23824 KB Output is correct
4 Correct 14 ms 23756 KB Output is correct
5 Correct 15 ms 23760 KB Output is correct
6 Correct 19 ms 23756 KB Output is correct
7 Correct 15 ms 23756 KB Output is correct
8 Correct 15 ms 23756 KB Output is correct
9 Correct 18 ms 23756 KB Output is correct
10 Correct 17 ms 23788 KB Output is correct
11 Correct 19 ms 23864 KB Output is correct
12 Correct 19 ms 23884 KB Output is correct
13 Correct 18 ms 23884 KB Output is correct
14 Correct 23 ms 23916 KB Output is correct
15 Correct 23 ms 24020 KB Output is correct
16 Correct 22 ms 24016 KB Output is correct
17 Correct 18 ms 23980 KB Output is correct
18 Correct 19 ms 23948 KB Output is correct
19 Correct 2011 ms 81740 KB Output is correct
20 Correct 2052 ms 95532 KB Output is correct
21 Correct 2020 ms 95452 KB Output is correct
22 Correct 1936 ms 95552 KB Output is correct
23 Correct 1626 ms 91436 KB Output is correct
24 Correct 141 ms 28020 KB Output is correct
25 Correct 132 ms 27432 KB Output is correct
26 Correct 117 ms 27248 KB Output is correct
27 Correct 118 ms 27452 KB Output is correct
28 Correct 138 ms 27500 KB Output is correct
29 Correct 97 ms 26576 KB Output is correct
30 Correct 104 ms 26584 KB Output is correct
31 Correct 119 ms 27540 KB Output is correct
32 Correct 60 ms 25500 KB Output is correct
33 Correct 121 ms 27536 KB Output is correct
34 Correct 423 ms 32192 KB Output is correct
35 Correct 324 ms 32148 KB Output is correct
36 Correct 295 ms 30772 KB Output is correct
37 Correct 282 ms 30848 KB Output is correct
38 Correct 332 ms 30732 KB Output is correct
39 Correct 231 ms 29604 KB Output is correct
40 Correct 220 ms 29520 KB Output is correct
41 Correct 302 ms 30176 KB Output is correct
42 Correct 297 ms 30128 KB Output is correct
43 Correct 324 ms 30276 KB Output is correct
44 Correct 325 ms 31092 KB Output is correct
45 Correct 284 ms 31036 KB Output is correct
46 Correct 324 ms 31028 KB Output is correct
47 Correct 293 ms 30996 KB Output is correct
48 Correct 286 ms 30956 KB Output is correct
49 Correct 233 ms 29192 KB Output is correct
50 Correct 226 ms 29104 KB Output is correct
51 Correct 218 ms 29120 KB Output is correct
52 Correct 200 ms 29072 KB Output is correct
53 Correct 216 ms 29172 KB Output is correct
54 Correct 253 ms 30468 KB Output is correct
55 Correct 178 ms 29624 KB Output is correct
56 Correct 256 ms 31216 KB Output is correct
57 Correct 1914 ms 97592 KB Output is correct
58 Correct 1837 ms 97524 KB Output is correct
59 Correct 1762 ms 93952 KB Output is correct
60 Correct 1845 ms 93908 KB Output is correct
61 Correct 2007 ms 93884 KB Output is correct
62 Correct 1763 ms 93984 KB Output is correct
63 Correct 1288 ms 81580 KB Output is correct
64 Correct 1130 ms 81440 KB Output is correct
65 Correct 1496 ms 89468 KB Output is correct
66 Correct 1530 ms 89476 KB Output is correct
67 Correct 1498 ms 89728 KB Output is correct
68 Correct 1495 ms 93448 KB Output is correct
69 Correct 1559 ms 93344 KB Output is correct
70 Correct 1549 ms 92720 KB Output is correct
71 Correct 1500 ms 92880 KB Output is correct
72 Correct 1513 ms 92780 KB Output is correct
73 Correct 1081 ms 79524 KB Output is correct
74 Correct 1055 ms 80408 KB Output is correct
75 Correct 1240 ms 79468 KB Output is correct
76 Correct 1220 ms 79536 KB Output is correct
77 Correct 1059 ms 79772 KB Output is correct
78 Correct 1394 ms 83052 KB Output is correct
79 Correct 924 ms 73320 KB Output is correct
80 Correct 1454 ms 84608 KB Output is correct