Submission #1110576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110576		_uros9	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	1288 ms	165432 KiB

sortbooks

#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,stek2;
    stek1.push({0,INF});
    stek2.push({0,-INF});
    for(int i=1; i<=n; i++){
        while(stek1.top().second<niz[i]) stek1.pop();
        while(stek2.top().second>niz[i]) stek2.pop();
        upd(1,1,N,stek1.top().first,stek1.top().second+niz[i]);
        //upd(1,1,N,stek2.top().first,stek2.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]});
        stek2.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 (stderr)

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: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23