oj.uz

Submission #418054

# Submission time Handle Problem Language Result Execution time Memory
418054 2021-06-05T01:09:22 Z Chaska Fire (JOI20_ho_t5) C++11
0 / 100
 299 ms 19904 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define ll long long
using namespace std;
typedef pair<long long,long long> ii;
typedef pair<int,ii> i3;

const int N = 2e5+5;
i3 x[N];
ll n,q;
ll a[N],b[N];
ll st[4*N],lz[4*N];
void ini(int no,int u,int v)
{
    if (u==v) {
        st[no] = a[u];
        return;
    }
    int mid = (u+v)/2;
    ini(no*2+1,u,mid);
    ini(no*2+2,mid+1,v);
    st[no] = max(st[no*2+1],st[no*2+2]);
    return;
}
ll r;
ll act[N];
void get(int no,int in,int fin,int u)
{
    if (fin < u || in > u) {
        st[no] = max(st[no],lz[no]);
        if (in != fin) {
            lz[no*2+1] = max(lz[no*2+1],lz[no]);
            lz[no*2+2] = max(lz[no*2+2],lz[no]);
        }
        return;
    }
    if (u<=in && fin <= u) {

        st[no] = max(st[no],lz[no]);
        if (in != fin) {
            lz[no*2+1] = max(lz[no*2+1],lz[no]);
            lz[no*2+2] = max(lz[no*2+2],lz[no]);
        }
        r = max(r,st[no]);
        return;
    }
            st[no] = max(st[no],lz[no]);
    int mid= (in+fin)/2;
    get(no*2+1,in,mid,u);
    get(no*2+2,mid+1,fin,u);
    return;
}
void upd(int no,int in,int fin,int u,int v,ll val)
{
    if(fin < u || in > v) {
        st[no] = max(st[no],lz[no]);
        if (in != fin) {
            lz[no*2+1] = max(lz[no*2+1],lz[no]);
            lz[no*2+2] = max(lz[no*2+2],lz[no]);
        }
        return;
    }
    if (u<=in && fin <= v) {
        lz[no] = max(lz[no],val);
        st[no] = max(st[no],lz[no]);
        if (in != fin) {
            lz[no*2+1] = max(lz[no*2+1],lz[no]);
            lz[no*2+2] = max(lz[no*2+2],lz[no]);
        }
        return;
    }
    int mid = (in+fin)/2;
            st[no] = max(st[no],lz[no]);
    upd(no*2+1,in,mid,u,v,val);
    upd(no*2+2,mid+1,fin,u,v,val);
    st[no] = max(st[no*2+1],st[no*2+2]);
    return;
}
int main()
{
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> q;
    for (int i=1;i<=n;i++) 
        cin >> a[i];
    for (int i=0;i<q;i++) cin >> x[i].F >> x[i].S.F >> x[i].S.S;
    ini(0,1,n);
    int k = x[0].F;
    for (ll i=1;i<=n;i++) {
        upd(0,1,n,i,min(n,i+k),a[i]);
    }
    for (int i=1;i<=n;i++) {
        r = 0;
        get(0,1,n,i);
        a[i] = r;
        act[i] = a[i] + act[i-1];
    }
    for (int i=0;i<q;i++) {
        cout << act[x[i].S.S] - act[x[i].S.F-1] << "\n";
    }
    return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

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