oj.uz

Submission #1110576

# Submission time Handle Problem Language Result Execution time Memory
1110576 2024-11-09T22:41:41 Z _uros9 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 1288 ms 165432 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,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

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.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57936 KB Output is correct
2 Correct 10 ms 58104 KB Output is correct
3 Correct 9 ms 58040 KB Output is correct
4 Correct 10 ms 57936 KB Output is correct
5 Correct 9 ms 57936 KB Output is correct
6 Correct 10 ms 57972 KB Output is correct
7 Correct 10 ms 57936 KB Output is correct
8 Correct 10 ms 57936 KB Output is correct
9 Correct 11 ms 57936 KB Output is correct
10 Incorrect 10 ms 57936 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57936 KB Output is correct
2 Correct 10 ms 58104 KB Output is correct
3 Correct 9 ms 58040 KB Output is correct
4 Correct 10 ms 57936 KB Output is correct
5 Correct 9 ms 57936 KB Output is correct
6 Correct 10 ms 57972 KB Output is correct
7 Correct 10 ms 57936 KB Output is correct
8 Correct 10 ms 57936 KB Output is correct
9 Correct 11 ms 57936 KB Output is correct
10 Incorrect 10 ms 57936 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 116344 KB Output is correct
2 Correct 1184 ms 149172 KB Output is correct
3 Correct 1261 ms 149064 KB Output is correct
4 Correct 1288 ms 149176 KB Output is correct
5 Incorrect 1126 ms 165432 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57936 KB Output is correct
2 Correct 10 ms 58104 KB Output is correct
3 Correct 9 ms 58040 KB Output is correct
4 Correct 10 ms 57936 KB Output is correct
5 Correct 9 ms 57936 KB Output is correct
6 Correct 10 ms 57972 KB Output is correct
7 Correct 10 ms 57936 KB Output is correct
8 Correct 10 ms 57936 KB Output is correct
9 Correct 11 ms 57936 KB Output is correct
10 Incorrect 10 ms 57936 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 57936 KB Output is correct
2 Correct 10 ms 58104 KB Output is correct
3 Correct 9 ms 58040 KB Output is correct
4 Correct 10 ms 57936 KB Output is correct
5 Correct 9 ms 57936 KB Output is correct
6 Correct 10 ms 57972 KB Output is correct
7 Correct 10 ms 57936 KB Output is correct
8 Correct 10 ms 57936 KB Output is correct
9 Correct 11 ms 57936 KB Output is correct
10 Incorrect 10 ms 57936 KB Output isn't correct
11 Halted 0 ms 0 KB -