oj.uz

Submission #115860

# Submission time Handle Problem Language Result Execution time Memory
115860 2019-06-09T11:15:52 Z someone_aa Foehn Phenomena (JOI17_foehn_phenomena) C++17
100 / 100
 670 ms 20044 KB 
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
using namespace std;
const int maxn = 200100;
ll n, q, s, t;
ll a[maxn];

ll tree[4*maxn];
ll lazy[4*maxn];

void push_update(int li, int ri, int index) {
    if(lazy[index] != 0) {
        tree[index] += lazy[index];
        if(li != ri) {
            lazy[2*index] += lazy[index];
            lazy[2*index+1] += lazy[index];
        }
        lazy[index] = 0;
    }
}

void build(int li=0, int ri=n, int index=1) {
    if(li == ri) {
        tree[index] = a[li];
    }
    else {
        int mid = (li + ri) / 2;
        build(li, mid, 2*index);
        build(mid+1, ri, 2*index+1);
    }
}

void update(int ul, int ur, ll uval, int li=0, int ri=n, int index=1) {
    push_update(li, ri, index);
    if(li > ur || ri < ul) return;
    else if(li >= ul && ri <= ur) {
        lazy[index] += uval;
        push_update(li, ri, index);
    }
    else {
        int mid = (li + ri) / 2;
        update(ul,ur,uval,li,mid,2*index);
        update(ul,ur,uval,mid+1,ri,2*index+1);
        tree[index] = max(tree[2*index], tree[2*index+1]);
    }
}

ll query(int qind, int li=0, int ri=n, int index=1) {
    push_update(li, ri, index);
    if(li == ri) return tree[index];
    else {
        int mid = (li + ri) / 2;
        ll x;
        if(qind <= mid) x = query(qind, li, mid, 2*index);
        else x = query(qind, mid+1, ri, 2*index+1);

        tree[index] =  max(tree[2*index], tree[2*index+1]);
        return x;
    }
}

ll f(int i) {
    if(i == n) return 0LL;

    ll in = query(i+1);
    ll ic = query(i);

    ll diff = abs(in - ic);

    if(ic < in) return -diff * s;
    else return diff*t;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>q>>s>>t;
    for(int i=0;i<=n;i++) {
        cin>>a[i];
    }

    build();
    ll result = 0LL;
    for(int i=0;i<=n;i++) {
        result += f(i);
    }

    ll l, r, v;
    while(q--) {
        cin>>l>>r>>v;

        result -= f(l-1);
        result -= f(r);
        update(l, r, v);

        result += f(l-1);
        result += f(r);

        cout<<result<<"\n";
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 6 ms 568 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 4 ms 512 KB Output is correct
15 Correct 6 ms 512 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 4 ms 512 KB Output is correct
18 Correct 4 ms 512 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 17248 KB Output is correct
2 Correct 626 ms 17740 KB Output is correct
3 Correct 628 ms 18216 KB Output is correct
4 Correct 603 ms 17656 KB Output is correct
5 Correct 616 ms 18808 KB Output is correct
6 Correct 262 ms 13744 KB Output is correct
7 Correct 269 ms 13660 KB Output is correct
8 Correct 503 ms 18528 KB Output is correct
9 Correct 524 ms 18852 KB Output is correct
10 Correct 572 ms 17768 KB Output is correct
11 Correct 328 ms 13560 KB Output is correct
12 Correct 274 ms 14424 KB Output is correct
13 Correct 271 ms 14584 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 6 ms 568 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 6 ms 512 KB Output is correct
13 Correct 4 ms 512 KB Output is correct
14 Correct 4 ms 512 KB Output is correct
15 Correct 6 ms 512 KB Output is correct
16 Correct 4 ms 512 KB Output is correct
17 Correct 4 ms 512 KB Output is correct
18 Correct 4 ms 512 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 623 ms 17248 KB Output is correct
23 Correct 626 ms 17740 KB Output is correct
24 Correct 628 ms 18216 KB Output is correct
25 Correct 603 ms 17656 KB Output is correct
26 Correct 616 ms 18808 KB Output is correct
27 Correct 262 ms 13744 KB Output is correct
28 Correct 269 ms 13660 KB Output is correct
29 Correct 503 ms 18528 KB Output is correct
30 Correct 524 ms 18852 KB Output is correct
31 Correct 572 ms 17768 KB Output is correct
32 Correct 328 ms 13560 KB Output is correct
33 Correct 274 ms 14424 KB Output is correct
34 Correct 271 ms 14584 KB Output is correct
35 Correct 636 ms 17184 KB Output is correct
36 Correct 670 ms 18796 KB Output is correct
37 Correct 643 ms 19284 KB Output is correct
38 Correct 626 ms 19184 KB Output is correct
39 Correct 651 ms 19320 KB Output is correct
40 Correct 610 ms 19224 KB Output is correct
41 Correct 611 ms 19024 KB Output is correct
42 Correct 608 ms 19056 KB Output is correct
43 Correct 618 ms 18316 KB Output is correct
44 Correct 603 ms 18812 KB Output is correct
45 Correct 623 ms 18744 KB Output is correct
46 Correct 627 ms 20044 KB Output is correct
47 Correct 271 ms 14200 KB Output is correct
48 Correct 321 ms 14256 KB Output is correct
49 Correct 650 ms 17324 KB Output is correct
50 Correct 336 ms 14036 KB Output is correct
51 Correct 272 ms 14504 KB Output is correct
52 Correct 390 ms 14200 KB Output is correct