oj.uz

Submission #1095135

# Submission time Handle Problem Language Result Execution time Memory
1095135 2024-10-01T11:15:36 Z KasymK Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1136 ms 126480 KB 
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 1e6+6;
const int INF = 2e9;
int v[N], id[N], l[N], r[N], k[N], ans[N];
vector<int> Q[N];

struct node{
    int l, r, val;
} seg[N<<2];

void build(int x, int l, int r){
    seg[x].l = l, seg[x].r = r;
    if(l == r){
        seg[x].val = -INF;
        return;
    }
    int mid = (l+r)>>1;
    build(x<<1, l, mid);
    build(x<<1|1, mid+1, r);
    seg[x].val = max(seg[x<<1].val, seg[x<<1|1].val);
}

void update(int x, int k, int u){
    if(seg[x].l == seg[x].r){
        seg[x].val = u;
        return;
    }
    int mid = (seg[x].l+seg[x].r)>>1;
    if(k <= mid)
        update(x<<1, k, u);
    else
        update(x<<1|1, k, u);
    seg[x].val = max(seg[x<<1].val, seg[x<<1|1].val);
}

int query(int x, int l, int r){
    if(seg[x].l == l and seg[x].r == r)
        return seg[x].val;
    int mid = (seg[x].l+seg[x].r)>>1;
    if(r <= mid)
        return query(x<<1, l, r);
    else if(l > mid)
        return query(x<<1|1, l, r);
    else
        return max(query(x<<1, l, mid), query(x<<1|1, mid+1, r));
}

int main(){
    // freopen("file.txt", "r", stdin);
    int n, q;
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; ++i){
        int x;
        scanf("%d", &x);
        v[i] = x;
    }
    stack<int> st;
    for(int i = 1; i <= n; ++i){
        while(!st.empty() and v[st.top()] <= v[i])
            st.pop();
        if(st.empty())
            id[i] = -1;
        else
            id[i] = st.top();
        st.push(i);
    }
    // for(int i = 1; i <= n; ++i)
    //     printf("%d ", id[i]);
    // puts("");
    // wr;
    for(int i = 1; i <= q; ++i){
        scanf("%d%d%d", &l[i], &r[i], &k[i]);
        Q[r[i]].pb(i);
    }
    build(1, 1, n);
    for(int j = 1; j <= n; ++j){
        int i = id[j];
        if(~i)
            update(1, i, v[i]+v[j]);
        for(auto &ww : Q[j])
            ans[ww] = (query(1, l[ww], r[ww]) <= k[ww]);
    }
    for(int i = 1; i <= q; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
sortbooks.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         scanf("%d%d%d", &l[i], &r[i], &k[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33112 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 5 ms 31064 KB Output is correct
5 Correct 5 ms 33116 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 5 ms 31068 KB Output is correct
8 Correct 5 ms 31068 KB Output is correct
9 Correct 5 ms 31068 KB Output is correct
10 Correct 5 ms 31068 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33112 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 5 ms 31064 KB Output is correct
5 Correct 5 ms 33116 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 5 ms 31068 KB Output is correct
8 Correct 5 ms 31068 KB Output is correct
9 Correct 5 ms 31068 KB Output is correct
10 Correct 5 ms 31068 KB Output is correct
11 Correct 6 ms 31324 KB Output is correct
12 Correct 7 ms 31436 KB Output is correct
13 Correct 7 ms 33624 KB Output is correct
14 Correct 7 ms 31580 KB Output is correct
15 Correct 7 ms 31516 KB Output is correct
16 Correct 7 ms 31580 KB Output is correct
17 Correct 8 ms 33356 KB Output is correct
18 Correct 8 ms 31580 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1136 ms 125260 KB Output is correct
2 Correct 1084 ms 126236 KB Output is correct
3 Correct 1131 ms 126140 KB Output is correct
4 Correct 1126 ms 126460 KB Output is correct
5 Correct 1004 ms 126480 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 41300 KB Output is correct
2 Correct 66 ms 40528 KB Output is correct
3 Correct 60 ms 41020 KB Output is correct
4 Correct 63 ms 41184 KB Output is correct
5 Correct 65 ms 39404 KB Output is correct
6 Correct 51 ms 39916 KB Output is correct
7 Correct 51 ms 38040 KB Output is correct
8 Correct 59 ms 38864 KB Output is correct
9 Correct 33 ms 34264 KB Output is correct
10 Correct 65 ms 39116 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33112 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 5 ms 31064 KB Output is correct
5 Correct 5 ms 33116 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 5 ms 31068 KB Output is correct
8 Correct 5 ms 31068 KB Output is correct
9 Correct 5 ms 31068 KB Output is correct
10 Correct 5 ms 31068 KB Output is correct
11 Correct 6 ms 31324 KB Output is correct
12 Correct 7 ms 31436 KB Output is correct
13 Correct 7 ms 33624 KB Output is correct
14 Correct 7 ms 31580 KB Output is correct
15 Correct 7 ms 31516 KB Output is correct
16 Correct 7 ms 31580 KB Output is correct
17 Correct 8 ms 33356 KB Output is correct
18 Correct 8 ms 31580 KB Output is correct
19 Correct 161 ms 52308 KB Output is correct
20 Correct 187 ms 50688 KB Output is correct
21 Correct 143 ms 48864 KB Output is correct
22 Correct 147 ms 48728 KB Output is correct
23 Correct 153 ms 52180 KB Output is correct
24 Correct 117 ms 50332 KB Output is correct
25 Correct 114 ms 50404 KB Output is correct
26 Correct 130 ms 51184 KB Output is correct
27 Correct 133 ms 51276 KB Output is correct
28 Correct 131 ms 51540 KB Output is correct
29 Correct 150 ms 52304 KB Output is correct
30 Correct 156 ms 52520 KB Output is correct
31 Correct 154 ms 52304 KB Output is correct
32 Correct 137 ms 52308 KB Output is correct
33 Correct 149 ms 52304 KB Output is correct
34 Correct 111 ms 48200 KB Output is correct
35 Correct 114 ms 46420 KB Output is correct
36 Correct 106 ms 46164 KB Output is correct
37 Correct 104 ms 49748 KB Output is correct
38 Correct 137 ms 46416 KB Output is correct
39 Correct 135 ms 47028 KB Output is correct
40 Correct 137 ms 44528 KB Output is correct
41 Correct 122 ms 48580 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 33112 KB Output is correct
2 Correct 5 ms 33116 KB Output is correct
3 Correct 5 ms 31068 KB Output is correct
4 Correct 5 ms 31064 KB Output is correct
5 Correct 5 ms 33116 KB Output is correct
6 Correct 5 ms 31068 KB Output is correct
7 Correct 5 ms 31068 KB Output is correct
8 Correct 5 ms 31068 KB Output is correct
9 Correct 5 ms 31068 KB Output is correct
10 Correct 5 ms 31068 KB Output is correct
11 Correct 6 ms 31324 KB Output is correct
12 Correct 7 ms 31436 KB Output is correct
13 Correct 7 ms 33624 KB Output is correct
14 Correct 7 ms 31580 KB Output is correct
15 Correct 7 ms 31516 KB Output is correct
16 Correct 7 ms 31580 KB Output is correct
17 Correct 8 ms 33356 KB Output is correct
18 Correct 8 ms 31580 KB Output is correct
19 Correct 1136 ms 125260 KB Output is correct
20 Correct 1084 ms 126236 KB Output is correct
21 Correct 1131 ms 126140 KB Output is correct
22 Correct 1126 ms 126460 KB Output is correct
23 Correct 1004 ms 126480 KB Output is correct
24 Correct 72 ms 41300 KB Output is correct
25 Correct 66 ms 40528 KB Output is correct
26 Correct 60 ms 41020 KB Output is correct
27 Correct 63 ms 41184 KB Output is correct
28 Correct 65 ms 39404 KB Output is correct
29 Correct 51 ms 39916 KB Output is correct
30 Correct 51 ms 38040 KB Output is correct
31 Correct 59 ms 38864 KB Output is correct
32 Correct 33 ms 34264 KB Output is correct
33 Correct 65 ms 39116 KB Output is correct
34 Correct 161 ms 52308 KB Output is correct
35 Correct 187 ms 50688 KB Output is correct
36 Correct 143 ms 48864 KB Output is correct
37 Correct 147 ms 48728 KB Output is correct
38 Correct 153 ms 52180 KB Output is correct
39 Correct 117 ms 50332 KB Output is correct
40 Correct 114 ms 50404 KB Output is correct
41 Correct 130 ms 51184 KB Output is correct
42 Correct 133 ms 51276 KB Output is correct
43 Correct 131 ms 51540 KB Output is correct
44 Correct 150 ms 52304 KB Output is correct
45 Correct 156 ms 52520 KB Output is correct
46 Correct 154 ms 52304 KB Output is correct
47 Correct 137 ms 52308 KB Output is correct
48 Correct 149 ms 52304 KB Output is correct
49 Correct 111 ms 48200 KB Output is correct
50 Correct 114 ms 46420 KB Output is correct
51 Correct 106 ms 46164 KB Output is correct
52 Correct 104 ms 49748 KB Output is correct
53 Correct 137 ms 46416 KB Output is correct
54 Correct 135 ms 47028 KB Output is correct
55 Correct 137 ms 44528 KB Output is correct
56 Correct 122 ms 48580 KB Output is correct
57 Correct 1103 ms 125224 KB Output is correct
58 Correct 1080 ms 125356 KB Output is correct
59 Correct 1018 ms 121168 KB Output is correct
60 Correct 949 ms 120984 KB Output is correct
61 Correct 963 ms 121184 KB Output is correct
62 Correct 973 ms 121388 KB Output is correct
63 Correct 669 ms 113340 KB Output is correct
64 Correct 586 ms 113336 KB Output is correct
65 Correct 856 ms 120652 KB Output is correct
66 Correct 881 ms 120520 KB Output is correct
67 Correct 879 ms 120912 KB Output is correct
68 Correct 963 ms 125384 KB Output is correct
69 Correct 964 ms 125264 KB Output is correct
70 Correct 901 ms 124492 KB Output is correct
71 Correct 888 ms 124496 KB Output is correct
72 Correct 917 ms 124436 KB Output is correct
73 Correct 566 ms 111452 KB Output is correct
74 Correct 556 ms 112336 KB Output is correct
75 Correct 564 ms 111440 KB Output is correct
76 Correct 577 ms 111280 KB Output is correct
77 Correct 572 ms 111184 KB Output is correct
78 Correct 854 ms 117444 KB Output is correct
79 Correct 598 ms 96116 KB Output is correct
80 Correct 824 ms 115128 KB Output is correct