Submission #1353896

#TimeUsernameProblemLanguageResultExecution timeMemory
1353896SulAFoehn Phenomena (JOI17_foehn_phenomena)C++20
100 / 100
245 ms6528 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;

int get_pos(vector<pair<int,int>>& A, int i, int j) {
    return ranges::find(A, pair{i, j}) - A.begin();
}

vector<vector<int>> Azzurro(int n, int l, string s) {
    s += string(51 - l, 'A');

    vector<pair<int,int>> diag[15];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            diag[i + j].emplace_back(i, j);
        }
    }
    vector<vector<int>> G(n, vector<int>(n));
    int p = 0;
    for (int d = 0; d < 15; d++) {
        if (diag[d].size() == 1) {
            G[ diag[d][0].first ][ diag[d][0].second ] = s[p++] - 'A';
            continue;
        }
        auto [si, sj] = diag[d][0];
        for (int k = 1; k < diag[d].size(); k++) {
            auto [i, j] = diag[d][k];
            G[i][j] = s[p++] - 'A';
            if (k % 2 == 0)
                G[si][sj] ^= G[i][j];
        }
    }
    return G;
}

string Bordeaux(int n, int l, vector<vector<int>> G) {
    string s = string(1, 'B' - G[0][0]);
    vector<pair<int,int>> diag[15];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            diag[i + j].emplace_back(i, j);
        }
    }
    int pi = 0, pj = 0;
    for (int d = 1; d < 15; d++) {
        int x = 0;
        for (int k = 0; k < diag[d].size(); k += 2) {
            auto [i, j] = diag[d][k];
            x ^= G[i][j];
        }
        int flip = x^1;
        int ni = pi, nj = pj;
        if (pi+1 < n && get_pos(diag[d], pi + 1, pj) % 2 == flip % 2) {
            ni++;
        } else {
            nj++;
        }
        for (int k = 1; k < diag[d].size(); k++) {
            auto [i, j] = diag[d][k];
            if (i == ni && j == nj) G[i][j] ^= 1;
            s += 'A' + G[i][j];
        }
        pi = ni, pj = nj;
    }
    s += 'B' - G[n-1][n-1];
    return s.substr(0, l);
}

int main() {
    int n, q, s, t; cin >> n >> q >> s >> t;
    int A[n+1];
    long long D[n];
    cin >> A[0];
    for (int i = 0; i < n; i++) {
        cin >> A[i+1];
        D[i] = A[i+1] - A[i];
    }

    long long ans = 0;
    auto add = [&](int i) { ans += abs(D[i])*(D[i] > 0 ? -s : t); };
    auto rem = [&](int i) { ans -= abs(D[i])*(D[i] > 0 ? -s : t); };
    auto update = [&](int i, int x) {
        if (i == n) return;
        rem(i);
        D[i] += x;
        add(i);
    };
    
    for (int i = 0; i < n; i++) add(i);
    while (q--) {
        int l,r,x; cin >> l >> r >> x;
        update(l-1, x);
        update(r, -x);
        cout<<ans<<"\n";
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...