oj.uz

Submission #1058816

# Submission time Handle Problem Language Result Execution time Memory
1058816 2024-08-14T14:05:28 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 734 ms 80824 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;
        for(int i = 1;i <= n;++i){ 
            cin>>w[i];
            jmp[i] = i - 1; 
            while(jmp[i] && w[i] >= w[jmp[i]]) jmp[i] = jmp[jmp[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,n) <= 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 26972 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 27060 KB Output is correct
4 Correct 4 ms 26968 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 4 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 3 ms 27100 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 26972 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 27060 KB Output is correct
4 Correct 4 ms 26968 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 4 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 3 ms 27100 KB Output is correct
11 Correct 4 ms 27224 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 5 ms 27484 KB Output is correct
15 Correct 6 ms 27484 KB Output is correct
16 Correct 5 ms 27356 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 5 ms 27320 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 80684 KB Output is correct
2 Correct 705 ms 80728 KB Output is correct
3 Correct 684 ms 80824 KB Output is correct
4 Correct 708 ms 80708 KB Output is correct
5 Incorrect 734 ms 70320 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31916 KB Output is correct
2 Correct 45 ms 33872 KB Output is correct
3 Incorrect 47 ms 33872 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 26972 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 27060 KB Output is correct
4 Correct 4 ms 26968 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 4 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 3 ms 27100 KB Output is correct
11 Correct 4 ms 27224 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 5 ms 27484 KB Output is correct
15 Correct 6 ms 27484 KB Output is correct
16 Correct 5 ms 27356 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 5 ms 27320 KB Output is correct
19 Correct 142 ms 45252 KB Output is correct
20 Correct 106 ms 45140 KB Output is correct
21 Correct 127 ms 44884 KB Output is correct
22 Correct 94 ms 44668 KB Output is correct
23 Correct 104 ms 44880 KB Output is correct
24 Incorrect 96 ms 42580 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 26972 KB Output is correct
2 Correct 3 ms 26972 KB Output is correct
3 Correct 3 ms 27060 KB Output is correct
4 Correct 4 ms 26968 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 4 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 3 ms 27100 KB Output is correct
11 Correct 4 ms 27224 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 5 ms 27484 KB Output is correct
15 Correct 6 ms 27484 KB Output is correct
16 Correct 5 ms 27356 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 5 ms 27320 KB Output is correct
19 Correct 708 ms 80684 KB Output is correct
20 Correct 705 ms 80728 KB Output is correct
21 Correct 684 ms 80824 KB Output is correct
22 Correct 708 ms 80708 KB Output is correct
23 Incorrect 734 ms 70320 KB Output isn't correct
24 Halted 0 ms 0 KB -