oj.uz

Submission #418055

# Submission time Handle Problem Language Result Execution time Memory
418055 2021-06-05T01:10:42 Z Chaska Fire (JOI20_ho_t5) C++11
6 / 100
 296 ms 25028 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;
            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]);
        }
    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]);
                    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]);
        }
    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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 263 ms 19152 KB Output is correct
3 Correct 241 ms 24708 KB Output is correct
4 Correct 285 ms 24752 KB Output is correct
5 Correct 269 ms 24900 KB Output is correct
6 Correct 296 ms 24328 KB Output is correct
7 Correct 274 ms 25028 KB Output is correct
8 Correct 288 ms 24772 KB Output is correct
9 Correct 281 ms 24824 KB Output is correct
10 Correct 261 ms 24624 KB Output is correct
11 Correct 263 ms 25020 KB Output is correct
12 Correct 258 ms 24504 KB Output is correct
13 Correct 292 ms 24556 KB Output is correct
14 Correct 271 ms 24408 KB Output is correct
15 Correct 277 ms 24616 KB Output is correct
16 Correct 290 ms 24516 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 17540 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 -