Submission #1051579

#TimeUsernameProblemLanguageResultExecution timeMemory
1051579VahanAbrahamFoehn Phenomena (JOI17_foehn_phenomena)C++17
100 / 100
400 ms13136 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string> #include <algorithm> #include <cstring> #include <cstdio> #include <sstream> #include <map> #include <stack> #include <set> #include <queue> #include <list> #include <unordered_set> #include <unordered_map> #include <math.h> #include <bitset> #include <cmath> #include <vector> #include <iomanip> #include <random> #include <chrono> #include <cassert> using namespace std; #define ll long long #define fr first #define sc second #define pb push_back #define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout); ll gcd(ll a, ll b) { if (a == 0 || b == 0) { return max(a, b); } if (a <= b) { return gcd(a, b % a); } else { return gcd(a % b, b); } } ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; } const int N = 300005; const ll oo = 100000000000000000, MOD = 1000000007; ll a[N], b[N]; ll t[4 * N]; void ubd1(int l, int r,ll val, int lx, int rx, int x) { if (lx > r || rx<l) { return; } if (l <= lx && rx <= r) { t[x] += val; return; } int m = (lx + rx) / 2; ubd1(l, r, val, lx, m, 2 * x); ubd1(l, r, val, m + 1, rx, 2 * x + 1); } ll get1(int ind, int l, int r, int x) { if (l == r) { return t[x] + a[l]; } int m = (l + r) / 2; if (ind <= m) { return t[x] + get1(ind, l, m, 2 * x); } else { return t[x] + get1(ind, m + 1, r, 2 * x + 1); } } //void build(int l, int r, int x) { // if (l == r) { // t1[x].v = 0; // t1[x].ans = b[l]; // t1[x].size = 1; // return; // } // int m = (l + r) / 2; // build(l, m, 2 * x); // build(m + 1, r, 2 * x + 1); // t1[x].v = 0; // t1[x].ans = t1[2 * x].ans + t1[2 * x + 1].ans; // t1[x].size = t1[2 * x].size + t1[2 * x + 1].size; //} // //void ubd1(int l,int r,) void solve() { int n, q; ll s, t; cin >> n >> q >> s >> t;; for (int i = 0; i <= n; ++i) { cin >> a[i]; } ll sum = 0; for (int i = 1; i <= n; ++i) { if (a[i] <= a[i - 1]) { b[i] = t * (a[i - 1] - a[i]); } else { b[i] = -((a[i] - a[i - 1]) * s); } sum += b[i]; } while (q--) { int l, r, x; cin >> l >> r >> x; ll val1 = get1(l, 0, n, 1); ll val2 = get1(l - 1, 0, n, 1); //cout << l << " " << val1 << " " << val2 << endl; if (val1 > val2) { sum -= -((val1 - val2) * s); } else { sum -= (val2 - val1) * t; } if (r < n) { val1 = get1(r, 0, n, 1); val2 = get1(r + 1, 0, n, 1); //cout <<"RR "<< r << " " << val1 << " " << val2 << endl; if (val1 < val2) { sum -= -((val2 - val1) * s); } else { sum -= ((val1 - val2) * t); } } ubd1(l, r, x, 0, n, 1); val1 = get1(l, 0, n, 1); val2 = get1(l - 1, 0, n, 1); if (val1 > val2) { sum += -((val1 - val2) * s); } else { sum += ((val2 - val1) * t); } if (r < n) { val1 = get1(r, 0, n, 1); val2 = get1(r + 1, 0, n, 1); if (val1 < val2) { sum += -((val2 - val1) * s); } else { sum += ((val1 - val2) * t); } } cout << sum << endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //US int tt = 1; //cin >> tt; while (tt--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...