oj.uz

Submission #1058882

# Submission time Handle Problem Language Result Execution time Memory
1058882 2024-08-14T14:42:59 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 750 ms 80900 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] = 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();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27224 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 27084 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 3 ms 27088 KB Output is correct
7 Correct 3 ms 26972 KB Output is correct
8 Correct 4 ms 26972 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27224 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 27084 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 3 ms 27088 KB Output is correct
7 Correct 3 ms 26972 KB Output is correct
8 Correct 4 ms 26972 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct
11 Correct 5 ms 27228 KB Output is correct
12 Correct 5 ms 27348 KB Output is correct
13 Correct 5 ms 27256 KB Output is correct
14 Correct 6 ms 27224 KB Output is correct
15 Correct 5 ms 27324 KB Output is correct
16 Correct 5 ms 27096 KB Output is correct
17 Correct 5 ms 27072 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 709 ms 80632 KB Output is correct
2 Correct 718 ms 80724 KB Output is correct
3 Correct 709 ms 80724 KB Output is correct
4 Correct 750 ms 80900 KB Output is correct
5 Incorrect 710 ms 67572 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 31980 KB Output is correct
2 Correct 49 ms 31824 KB Output is correct
3 Incorrect 50 ms 29688 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27224 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 27084 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 3 ms 27088 KB Output is correct
7 Correct 3 ms 26972 KB Output is correct
8 Correct 4 ms 26972 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct
11 Correct 5 ms 27228 KB Output is correct
12 Correct 5 ms 27348 KB Output is correct
13 Correct 5 ms 27256 KB Output is correct
14 Correct 6 ms 27224 KB Output is correct
15 Correct 5 ms 27324 KB Output is correct
16 Correct 5 ms 27096 KB Output is correct
17 Correct 5 ms 27072 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct
19 Correct 122 ms 38740 KB Output is correct
20 Correct 118 ms 38744 KB Output is correct
21 Correct 104 ms 38580 KB Output is correct
22 Correct 103 ms 38740 KB Output is correct
23 Correct 118 ms 38488 KB Output is correct
24 Incorrect 102 ms 34312 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27224 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 27084 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 3 ms 27088 KB Output is correct
7 Correct 3 ms 26972 KB Output is correct
8 Correct 4 ms 26972 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct
11 Correct 5 ms 27228 KB Output is correct
12 Correct 5 ms 27348 KB Output is correct
13 Correct 5 ms 27256 KB Output is correct
14 Correct 6 ms 27224 KB Output is correct
15 Correct 5 ms 27324 KB Output is correct
16 Correct 5 ms 27096 KB Output is correct
17 Correct 5 ms 27072 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct
19 Correct 709 ms 80632 KB Output is correct
20 Correct 718 ms 80724 KB Output is correct
21 Correct 709 ms 80724 KB Output is correct
22 Correct 750 ms 80900 KB Output is correct
23 Incorrect 710 ms 67572 KB Output isn't correct
24 Halted 0 ms 0 KB -