Submission #1058884

# Submission time Handle Problem Language Result Execution time Memory
1058884 2024-08-14T14:44:20 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
744 ms 80724 KB
#include <bits/stdc++.h>
#ifdef LOCAL
    #include "/home/trcmai/code/tools.h"
    #define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
    #define debug(x...)
#endif
using namespace std;
#define all(a) a.begin(), a.end()
#define ll long long
#define endl '\n'
const int N = 1e6 + 6, LOG = 27, MOD = 1e9 + 7;
const ll INF = 1e18;
int n,q,jmp[N]; 
ll w[N];
vector<tuple<int,int,ll>>Q[N];

ll tr[4*N];
void update(int i,int l,int r,int pos,ll val){
    if(l == r){
        tr[i] = max(tr[i],val); 
        return;
    }
    int m = (r+l) >> 1; 
    if(pos <= m) update(2*i,l,m,pos,val);
    else update(2*i+1,m+1,r,pos,val);
    tr[i] = max(tr[2*i],tr[2*i+1]);
}
ll get(int i,int l,int r,int ql,int qr){
    if(l > qr || r < ql) return 0;
    if(ql <= l && r <= qr) return tr[i];
    int m = (r+l) >> 1; 
    return max(get(2*i,l,m,ql,qr),get(2*i+1,m+1,r,ql,qr));
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    auto solver=[&](){
        cin>>n>>q;
        deque<int>dq;
        for(int i = 1;i <= n;++i){ 
            cin>>w[i];
            while(dq.size() && w[dq.back()] <= w[i]) dq.pop_back();
            if(dq.size()) jmp[i] = dq.back();
            dq.push_back(i);
        }
        for(int i = 1;i <= q;++i){
            int l,r; ll c; 
            cin>>l>>r>>c;
            Q[r].emplace_back(i,l,c);
        }
        vector<bool>res(q + 1);
        for(int i = 1;i <= n;++i){ 
            update(1,1,n,jmp[i],w[i] + w[jmp[i]]);
            for(auto [idx,l,c] : Q[i])
                res[idx] = (get(1,1,n,l,i) <= c);
        }
        for(int i = 1;i <= q;++i)
            cout<<res[i]<<endl;
    };
    int t = 1; // cin>>t;
    while (t--) solver();
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 26972 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 27052 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 3 ms 27152 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 27096 KB Output is correct
10 Correct 4 ms 26972 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 26972 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 27052 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 3 ms 27152 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 27096 KB Output is correct
10 Correct 4 ms 26972 KB Output is correct
11 Correct 4 ms 27240 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 5 ms 27224 KB Output is correct
14 Correct 6 ms 27480 KB Output is correct
15 Correct 5 ms 27404 KB Output is correct
16 Correct 5 ms 27228 KB Output is correct
17 Correct 5 ms 27100 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 744 ms 80676 KB Output is correct
2 Correct 732 ms 80720 KB Output is correct
3 Correct 719 ms 80644 KB Output is correct
4 Correct 703 ms 80724 KB Output is correct
5 Incorrect 721 ms 65616 KB Output isn't correct
6 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 53 ms 31828 KB Output is correct
2 Correct 51 ms 31796 KB Output is correct
3 Incorrect 52 ms 27732 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 26972 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 27052 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 3 ms 27152 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 27096 KB Output is correct
10 Correct 4 ms 26972 KB Output is correct
11 Correct 4 ms 27240 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 5 ms 27224 KB Output is correct
14 Correct 6 ms 27480 KB Output is correct
15 Correct 5 ms 27404 KB Output is correct
16 Correct 5 ms 27228 KB Output is correct
17 Correct 5 ms 27100 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct
19 Correct 118 ms 38740 KB Output is correct
20 Correct 117 ms 38652 KB Output is correct
21 Correct 106 ms 38412 KB Output is correct
22 Correct 111 ms 38484 KB Output is correct
23 Correct 108 ms 38484 KB Output is correct
24 Incorrect 108 ms 32308 KB Output isn't correct
25 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 26972 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 26972 KB Output is correct
5 Correct 3 ms 27052 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 3 ms 27152 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 27096 KB Output is correct
10 Correct 4 ms 26972 KB Output is correct
11 Correct 4 ms 27240 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 5 ms 27224 KB Output is correct
14 Correct 6 ms 27480 KB Output is correct
15 Correct 5 ms 27404 KB Output is correct
16 Correct 5 ms 27228 KB Output is correct
17 Correct 5 ms 27100 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct
19 Correct 744 ms 80676 KB Output is correct
20 Correct 732 ms 80720 KB Output is correct
21 Correct 719 ms 80644 KB Output is correct
22 Correct 703 ms 80724 KB Output is correct
23 Incorrect 721 ms 65616 KB Output isn't correct
24 Halted 0 ms 0 KB -