oj.uz

Submission #745576

# Submission time Handle Problem Language Result Execution time Memory
745576 2023-05-20T12:14:44 Z Pacybwoah Fire (JOI20_ho_t5) C++14
6 / 100
 171 ms 19916 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define ll long long
using namespace std;
vector<ll> seg;
vector<ll> vec;
void build(int l,int r,int ind){
    if(l==r){
        seg[ind]=vec[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ind*2);
    build(mid+1,r,ind*2+1);
    seg[ind]=max(seg[ind*2],seg[ind*2+1]);
}
ll query(int l,int r,int start,int end,int ind){
    if(r<start||end<l) return 0;
    if(start<=l&&r<=end) return seg[ind];
    int mid=(l+r)>>1;
    return max(query(l,mid,start,end,ind*2),query(mid+1,r,start,end,ind*2+1));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    vector<ll> f(n+1);
    seg.resize(4*n+4);
    for(int i=0;i<n;i++) cin>>f[i+1];
    vec.resize(n+1);
    for(int i=1;i<=n;i++) vec[i]=f[i];
    build(1,n,1);
    vector<ll> pre(n+1);
    int a,b,c;
    cin>>a>>b>>c;
    for(int i=1;i<=n;i++){
        pre[i]=query(1,n,max(1,i-a),i,1);
    }
    for(int i=2;i<=n;i++) pre[i]+=pre[i-1];
    cout<<pre[c]-pre[b-1]<<"\n";
    for(int i=1;i<q;i++){
        cin>>a>>b>>c;
        cout<<pre[c]-pre[b-1]<<"\n";
    }
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 120 ms 13784 KB Output is correct
3 Correct 113 ms 19456 KB Output is correct
4 Correct 132 ms 19496 KB Output is correct
5 Correct 146 ms 19792 KB Output is correct
6 Correct 126 ms 19364 KB Output is correct
7 Correct 122 ms 19660 KB Output is correct
8 Correct 136 ms 19748 KB Output is correct
9 Correct 134 ms 19756 KB Output is correct
10 Correct 127 ms 19388 KB Output is correct
11 Correct 122 ms 19916 KB Output is correct
12 Correct 117 ms 19344 KB Output is correct
13 Correct 136 ms 19568 KB Output is correct
14 Correct 127 ms 19424 KB Output is correct
15 Correct 171 ms 19580 KB Output is correct
16 Correct 141 ms 19472 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 134 ms 12948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -