oj.uz

Submission #33267

# Submission time Handle Problem Language Result Execution time Memory
33267 2017-10-23T07:48:06 Z minhtung0404 Foehn Phenomena (JOI17_foehn_phenomena) C++14
30 / 100
 423 ms 28580 KB 
#include<bits/stdc++.h>
const int N = 2e5 + 5;
using namespace std;

struct node {
    long long l, r, val, lazy;
} lv[4*N];

bool operator == (node a, node b){
    return ((a.l == b.l) && (a.r == b.r) && (a.val == b.val));
}

int n, q;
long long S, T, a[N];

node Merge_Node(node a, node b){
    node ans; ans.l = a.l, ans.r = b.r; ans.val = a.val + b.val; ans.lazy = 0;
    if (a.r >= b.l) ans.val += T*abs(a.r - b.l);
    else ans.val -= S*abs(b.l - a.r);
    return ans;
}

void dolazy(int i, int l, int r){
    if (lv[i].lazy == 0) return;
    lv[i].l += lv[i].lazy; lv[i].r += lv[i].lazy;
    if (l != r){
        lv[i*2].lazy += lv[i].lazy; lv[i*2+1].lazy += lv[i].lazy;
    }
    lv[i].lazy = 0;
}

void init(int i, int l, int r){
    if (l == r){
        lv[i].l = lv[i].r = a[l]; lv[i].val = 0;
        return;
    }
    int mid = (l + r) / 2;
    init(i*2, l, mid); init(i*2+1, mid+1, r);
    lv[i] = Merge_Node(lv[i*2], lv[i*2+1]);
}

void update(int i, int l, int r, int L, int R, long long val){
    dolazy(i, l, r);
    if (L > r || l > R) return;
    if (L <= l && r <= R) {
        lv[i].lazy += val; dolazy(i, l, r);
        return ;
    }
    int mid = (l + r) / 2;
    update(i*2, l, mid, L, R, val); update(i*2+1, mid+1, r, L, R, val);
    lv[i] = Merge_Node(lv[i*2], lv[i*2+1]);
}

int main(){
    cin >> n >> q >> S >> T;
    for (int i = 0; i <= n; i++) cin >> a[i];
    init(1, 0, n);
    while (q--){
        long long l, r, val;
        cin >> l >> r >> val;
        update(1, 0, n, l, r, val);
        printf("%lld\n", lv[1].val);
    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 423 ms 28580 KB Execution timed out (wall clock limit exceeded)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 28580 KB Output is correct
2 Correct 23 ms 28580 KB Output is correct
3 Correct 9 ms 28580 KB Output is correct
4 Correct 3 ms 28580 KB Output is correct
5 Correct 3 ms 28580 KB Output is correct
6 Correct 9 ms 28580 KB Output is correct
7 Correct 9 ms 28580 KB Output is correct
8 Correct 23 ms 28580 KB Output is correct
9 Correct 3 ms 28580 KB Output is correct
10 Correct 13 ms 28580 KB Output is correct
11 Correct 13 ms 28580 KB Output is correct
12 Correct 9 ms 28580 KB Output is correct
13 Correct 9 ms 28580 KB Output is correct
14 Correct 3 ms 28580 KB Output is correct
15 Correct 6 ms 28580 KB Output is correct
16 Correct 6 ms 28580 KB Output is correct
17 Correct 9 ms 28580 KB Output is correct
18 Correct 26 ms 28580 KB Output is correct
19 Correct 0 ms 28580 KB Output is correct
20 Correct 0 ms 28580 KB Output is correct
21 Correct 0 ms 28580 KB Output is correct
22 Runtime error 423 ms 28580 KB Execution timed out (wall clock limit exceeded)
23 Halted 0 ms 0 KB -