제출 #376421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376421		smjleo	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	206 ms	14828 KiB

foehn_phenomena

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int long long
#define nl '\n'
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int mod = 1000000007, mod2 = 998244353;

// change this
const int N = 200005;

int n, q, s, t, arr[N], ans;

int delta(int x, int y) {
    if (x < y) return -s * (y-x);
    else return t * (x-y);
}

int fw[N], fw2[N];
void update(int x, int y, int v) { //inclusive
    for (int tx=x; tx < N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
    for (int ty=y+1; ty < N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
}
int sum (int x) {
    int res = 0;
    for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
    return res;
}
int point(int x) { //inclusive
    if (x == 0) return 0;
    return sum(x) - sum(x-1);
}

signed main() {
    io;
    cin >> n >> q >> s >> t;
    n++;
    for (int i=0; i<n; i++) {
        cin >> arr[i];
        if (i) update(i, i, arr[i]);
    }
    for (int i=1; i<n; i++) {
        ans += delta(arr[i-1], arr[i]);
    }

    while (q--) {
        int a, b, c;
        cin >> a >> b >> c;
        int dx = delta(point(a-1), point(a) + c) - delta(point(a-1), point(a));
        int dy = delta(point(b) + c, point(b+1)) - delta(point(b), point(b+1));
        update(a, b, c);
        if (b == n-1) dy = 0;
        cout << (ans += dx + dy) << nl;
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 10 / 10
• Subtask 3: 60 / 60