# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
158023 | ZwariowanyMarcin | Foehn Phenomena (JOI17_foehn_phenomena) | C++14 | 301 ms | 5980 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;
#define ios cin.tie(0); ios_base::sync_with_stdio(0)
using namespace std;
int n, q;
int a[200000 + 111];
ll res = 0;
int s, t;
int l, r, x;
struct fenwick {
ll add[200000 + 111];
void init() {
FOR(i, 1, 200000)
add[i] = 0;
}
void dodaj(int x, int c) {
for(; x <= 200000; x += x & -x)
add[x] += c;
}
ll daj(int x) {
ll res = 0;
for(; 0 < x; x -= x & -x)
res += add[x];
return res;
}
ll sum(int id) {
return daj(200000) - daj(id - 1);
}
} ja;
void roll(int x) {
if(x <= 1 || x > n + 1)
return;
int k = abs(ja.sum(x) - ja.sum(x - 1));
if(ja.sum(x) > ja.sum(x - 1))
res += (ll) s * k;
else
res -= (ll) t * k;
}
void akt(int x) {
if(x <= 1 || x > n + 1)
return;
int k = abs(ja.sum(x) - ja.sum(x - 1));
if(ja.sum(x) > ja.sum(x - 1))
res -= (ll) s * k;
else
res += (ll) t * k;
}
int main() {
ja.init();
scanf("%d %d %d %d", &n, &q, &s, &t);
FOR(i, 1, n + 1)
scanf("%d", &a[i]);
FOR(i, 2, n + 1) {
ja.dodaj(i, a[i]);
ja.dodaj(i - 1, -a[i]);
}
FOR(i, 2, n + 1)
akt(i);
FOR(i, 1, q) {
scanf("%d %d %d", &l, &r, &x);
l += 1;
r += 1;
roll(l);
roll(r + 1);
ja.dodaj(r, x);
ja.dodaj(l - 1, -x);
akt(l);
akt(r + 1);
printf("%lld\n", res);
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |