# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
158023 | ZwariowanyMarcin | Foehn Phenomena (JOI17_foehn_phenomena) | C++14 | 301 ms | 5980 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (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... |