oj.uz

Submission #1110581

# Submission time Handle Problem Language Result Execution time Memory
1110581 2024-11-10T02:07:45 Z _uros9 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1238 ms 150956 KB 
#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const long long longlongmax=9223372036854775807;
const int modul=998244353;
const long long mod = 1e9 + 7;


mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

const int N=1000009,INF=1000000000009;
int n,q;
int niz[N],rez[N];
int seg[4*N];
struct Upit{
    int l,d,k,ind;
    Upit(){}
    Upit(int l,int d,int k,int ind){this->l=l;this->d=d;this->k=k;this->ind=ind;}
};
vector<Upit> Q[N];

void upd(int node,int l,int d,int ind,int val){
    if(l==d&&l==ind){seg[node]=max(seg[node],val); return;}
    if(d<ind||l>ind) return;
    int s=l+d>>1;
    upd(2*node,l,s,ind,val);upd(2*node+1,s+1,d,ind,val);
    seg[node]=max(seg[2*node],seg[2*node+1]);
}
int query(int node,int l,int d,int poc,int kr){
    if(poc<=l&&d<=kr) return seg[node];
    if(d<poc||l>kr) return -INF;
    int s=l+d>>1;
    return max(query(2*node,l,s,poc,kr),query(2*node+1,s+1,d,poc,kr));
}


signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("factory.in","r",stdin);
    //freopen("factory.out","w",stdout);



    for(int i=0; i<4*N; i++) seg[i]=-INF;
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> niz[i];
    for(int i=1; i<=q; i++){
        int l,d,k;
        cin >> l >> d >> k;
        Q[d].push_back(Upit(l,d,k,i));
    }
    stack<pair<int,int>> stek1;
    stek1.push({0,INF});
    for(int i=1; i<=n; i++){
        while(stek1.top().second<=niz[i]) stek1.pop();
        upd(1,1,N,stek1.top().first,stek1.top().second+niz[i]);
        for(auto x:Q[i]){
            rez[x.ind]=(query(1,1,N,x.l,x.d)<=x.k);
        }

        stek1.push({i,niz[i]});
    }
    for(int i=1; i<=q; i++) cout << rez[i] << endl;


    return 0;
}
/*
    abcde
    01234
    04321 --> 12340
              0   1
    011
    110

1
3 1
1 2 3
3 5

*/

Compilation message

sortbooks.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int s=l+d>>1;
      |           ~^~
sortbooks.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
sortbooks.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int s=l+d>>1;
      |           ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57936 KB Output is correct
2 Correct 13 ms 55268 KB Output is correct
3 Correct 13 ms 55288 KB Output is correct
4 Correct 17 ms 55120 KB Output is correct
5 Correct 16 ms 55120 KB Output is correct
6 Correct 16 ms 55120 KB Output is correct
7 Correct 16 ms 55120 KB Output is correct
8 Correct 17 ms 55196 KB Output is correct
9 Correct 15 ms 55120 KB Output is correct
10 Correct 16 ms 55232 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57936 KB Output is correct
2 Correct 13 ms 55268 KB Output is correct
3 Correct 13 ms 55288 KB Output is correct
4 Correct 17 ms 55120 KB Output is correct
5 Correct 16 ms 55120 KB Output is correct
6 Correct 16 ms 55120 KB Output is correct
7 Correct 16 ms 55120 KB Output is correct
8 Correct 17 ms 55196 KB Output is correct
9 Correct 15 ms 55120 KB Output is correct
10 Correct 16 ms 55232 KB Output is correct
11 Correct 19 ms 55436 KB Output is correct
12 Correct 19 ms 55392 KB Output is correct
13 Correct 25 ms 55376 KB Output is correct
14 Correct 25 ms 55800 KB Output is correct
15 Correct 23 ms 55632 KB Output is correct
16 Correct 25 ms 55912 KB Output is correct
17 Correct 15 ms 55644 KB Output is correct
18 Correct 17 ms 55632 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1169 ms 120020 KB Output is correct
2 Correct 1133 ms 132936 KB Output is correct
3 Correct 1238 ms 132784 KB Output is correct
4 Correct 1225 ms 116140 KB Output is correct
5 Correct 1052 ms 132936 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 62720 KB Output is correct
2 Correct 87 ms 63368 KB Output is correct
3 Correct 78 ms 63304 KB Output is correct
4 Correct 89 ms 63304 KB Output is correct
5 Correct 84 ms 63304 KB Output is correct
6 Correct 69 ms 63056 KB Output is correct
7 Correct 72 ms 63076 KB Output is correct
8 Correct 89 ms 62648 KB Output is correct
9 Correct 59 ms 61372 KB Output is correct
10 Correct 88 ms 62648 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57936 KB Output is correct
2 Correct 13 ms 55268 KB Output is correct
3 Correct 13 ms 55288 KB Output is correct
4 Correct 17 ms 55120 KB Output is correct
5 Correct 16 ms 55120 KB Output is correct
6 Correct 16 ms 55120 KB Output is correct
7 Correct 16 ms 55120 KB Output is correct
8 Correct 17 ms 55196 KB Output is correct
9 Correct 15 ms 55120 KB Output is correct
10 Correct 16 ms 55232 KB Output is correct
11 Correct 19 ms 55436 KB Output is correct
12 Correct 19 ms 55392 KB Output is correct
13 Correct 25 ms 55376 KB Output is correct
14 Correct 25 ms 55800 KB Output is correct
15 Correct 23 ms 55632 KB Output is correct
16 Correct 25 ms 55912 KB Output is correct
17 Correct 15 ms 55644 KB Output is correct
18 Correct 17 ms 55632 KB Output is correct
19 Correct 194 ms 74056 KB Output is correct
20 Correct 185 ms 73940 KB Output is correct
21 Correct 198 ms 74596 KB Output is correct
22 Correct 188 ms 74568 KB Output is correct
23 Correct 182 ms 74392 KB Output is correct
24 Correct 133 ms 74568 KB Output is correct
25 Correct 128 ms 74484 KB Output is correct
26 Correct 166 ms 74056 KB Output is correct
27 Correct 162 ms 74240 KB Output is correct
28 Correct 181 ms 76996 KB Output is correct
29 Correct 200 ms 74060 KB Output is correct
30 Correct 178 ms 73872 KB Output is correct
31 Correct 192 ms 74056 KB Output is correct
32 Correct 195 ms 75344 KB Output is correct
33 Correct 179 ms 73920 KB Output is correct
34 Correct 157 ms 74776 KB Output is correct
35 Correct 139 ms 73800 KB Output is correct
36 Correct 132 ms 73556 KB Output is correct
37 Correct 127 ms 73456 KB Output is correct
38 Correct 140 ms 73800 KB Output is correct
39 Correct 166 ms 71864 KB Output is correct
40 Correct 137 ms 71340 KB Output is correct
41 Correct 147 ms 71356 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57936 KB Output is correct
2 Correct 13 ms 55268 KB Output is correct
3 Correct 13 ms 55288 KB Output is correct
4 Correct 17 ms 55120 KB Output is correct
5 Correct 16 ms 55120 KB Output is correct
6 Correct 16 ms 55120 KB Output is correct
7 Correct 16 ms 55120 KB Output is correct
8 Correct 17 ms 55196 KB Output is correct
9 Correct 15 ms 55120 KB Output is correct
10 Correct 16 ms 55232 KB Output is correct
11 Correct 19 ms 55436 KB Output is correct
12 Correct 19 ms 55392 KB Output is correct
13 Correct 25 ms 55376 KB Output is correct
14 Correct 25 ms 55800 KB Output is correct
15 Correct 23 ms 55632 KB Output is correct
16 Correct 25 ms 55912 KB Output is correct
17 Correct 15 ms 55644 KB Output is correct
18 Correct 17 ms 55632 KB Output is correct
19 Correct 1169 ms 120020 KB Output is correct
20 Correct 1133 ms 132936 KB Output is correct
21 Correct 1238 ms 132784 KB Output is correct
22 Correct 1225 ms 116140 KB Output is correct
23 Correct 1052 ms 132936 KB Output is correct
24 Correct 111 ms 62720 KB Output is correct
25 Correct 87 ms 63368 KB Output is correct
26 Correct 78 ms 63304 KB Output is correct
27 Correct 89 ms 63304 KB Output is correct
28 Correct 84 ms 63304 KB Output is correct
29 Correct 69 ms 63056 KB Output is correct
30 Correct 72 ms 63076 KB Output is correct
31 Correct 89 ms 62648 KB Output is correct
32 Correct 59 ms 61372 KB Output is correct
33 Correct 88 ms 62648 KB Output is correct
34 Correct 194 ms 74056 KB Output is correct
35 Correct 185 ms 73940 KB Output is correct
36 Correct 198 ms 74596 KB Output is correct
37 Correct 188 ms 74568 KB Output is correct
38 Correct 182 ms 74392 KB Output is correct
39 Correct 133 ms 74568 KB Output is correct
40 Correct 128 ms 74484 KB Output is correct
41 Correct 166 ms 74056 KB Output is correct
42 Correct 162 ms 74240 KB Output is correct
43 Correct 181 ms 76996 KB Output is correct
44 Correct 200 ms 74060 KB Output is correct
45 Correct 178 ms 73872 KB Output is correct
46 Correct 192 ms 74056 KB Output is correct
47 Correct 195 ms 75344 KB Output is correct
48 Correct 179 ms 73920 KB Output is correct
49 Correct 157 ms 74776 KB Output is correct
50 Correct 139 ms 73800 KB Output is correct
51 Correct 132 ms 73556 KB Output is correct
52 Correct 127 ms 73456 KB Output is correct
53 Correct 140 ms 73800 KB Output is correct
54 Correct 166 ms 71864 KB Output is correct
55 Correct 137 ms 71340 KB Output is correct
56 Correct 147 ms 71356 KB Output is correct
57 Correct 1179 ms 149940 KB Output is correct
58 Correct 1137 ms 149772 KB Output is correct
59 Correct 1084 ms 150548 KB Output is correct
60 Correct 1083 ms 150572 KB Output is correct
61 Correct 1051 ms 150372 KB Output is correct
62 Correct 1051 ms 150320 KB Output is correct
63 Correct 682 ms 150956 KB Output is correct
64 Correct 690 ms 150892 KB Output is correct
65 Correct 903 ms 150476 KB Output is correct
66 Correct 929 ms 150088 KB Output is correct
67 Correct 928 ms 150348 KB Output is correct
68 Correct 1030 ms 149980 KB Output is correct
69 Correct 940 ms 149896 KB Output is correct
70 Correct 1008 ms 149860 KB Output is correct
71 Correct 973 ms 149832 KB Output is correct
72 Correct 994 ms 149864 KB Output is correct
73 Correct 630 ms 144200 KB Output is correct
74 Correct 676 ms 144712 KB Output is correct
75 Correct 614 ms 143888 KB Output is correct
76 Correct 608 ms 143944 KB Output is correct
77 Correct 663 ms 143388 KB Output is correct
78 Correct 912 ms 140980 KB Output is correct
79 Correct 720 ms 129012 KB Output is correct
80 Correct 988 ms 137092 KB Output is correct