oj.uz

Submission #1110461

# Submission time Handle Problem Language Result Execution time Memory
1110461 2024-11-09T13:54:25 Z _uros9 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 914 ms 74700 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];
int seg[4*N];
void upd(int node,int l,int d,int ind,int val){
    if(l==d&&l==ind){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);
}
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));
}
stack<pair<int,int>> stek;
int na_levog[N],na_desnog[N];


signed main(){

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

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



    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> niz[i];
    for(int i=0; i<=n+1; i++){na_desnog[i]=na_levog[i]=-INF;}
    stek.push({0,INF});
    for(int i=1; i<=n; i++){
        while(stek.top().second<niz[i]) stek.pop();
        na_levog[stek.top().first]=max(na_levog[stek.top().first],niz[stek.top().first]+niz[i]);
        stek.push({i,niz[i]});
    }
    while(stek.size()) stek.pop();
    stek.push({n+1,INF});
    for(int i=n; i>0; i--){
        while(stek.top().second<niz[i]) stek.pop();
        na_desnog[stek.top().first]=max(na_desnog[stek.top().first],niz[stek.top().first]+niz[i]);
        stek.push({i,niz[i]});
    }
    for(int i=1; i<=n; i++)
        upd(1,1,n,i,max(na_desnog[i],na_levog[i]));
    while(q--){
        int l,d,k;
        cin >> l >> d >> k;
        cout << (query(1,1,n,l,d)<=k) << 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:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     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:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |     int s=l+d>>1;
      |           ~^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Incorrect 2 ms 6624 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Incorrect 2 ms 6624 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 914 ms 74700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 16968 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Incorrect 2 ms 6624 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6480 KB Output is correct
2 Correct 2 ms 6480 KB Output is correct
3 Incorrect 2 ms 6624 KB Output isn't correct
4 Halted 0 ms 0 KB -