oj.uz

답안 #945725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
945725 2024-03-14T06:46:18 Z nasir_bashirov Foehn Phenomena (JOI17_foehn_phenomena) C++11
100 / 100
 543 ms 13084 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio\
    ios_base::sync_with_stdio(0);\
    cin.tie(0);\
    cout.tie(0)\
 
#define int long long
 
struct fenwickTree{
    int n;
    vi BIT;
    fenwickTree(int sz){
        n = sz;
        BIT.resize(n + 1, 0);
    }
    void update(int i, int v){
        if(i == 0)    return;
        while(i <= n){
            BIT[i] += v;
            i += i & (-i);
        }
    }
    int query(int l, int r){
        if(l > r)   return 0;   
        if(l != 1)    return query(1, r) - query(1, l - 1);
        int res = 0;
        while(r > 0){
            res += BIT[r];
            r -= r & (-r);
        }
        return res;
    }
};

const int sz = 2e5 + 5;
int n, q, x, y, l, r, k, res, a[sz];
 
signed main(){
    cin >> n >> q >> x >> y;
    fenwickTree t(n + 1);
    for(int i = 1; i <= n + 1; i++){
        cin >> a[i];
        t.update(i, a[i] - t.query(1, i - 1));
        if(i > 1){
            if(a[i] <= a[i - 1]) res += y * (a[i - 1] - a[i]);
            else    res -= x * (a[i] - a[i - 1]);
        }   
    }
    while(q--){
        cin >> l >> r >> k;
        l++, r++;
        if(l > 1 and t.query(1, l) <= t.query(1, l - 1))    res -= y * abs(t.query(1, l) - t.query(1, l - 1));
        else if(l > 1)    res += x * abs(t.query(1, l) - t.query(1, l - 1));
        if(r < n + 1 and t.query(1, r + 1) < t.query(1, r))    res -= y * abs(t.query(1, r + 1) - t.query(1, r));
        else if(r < n + 1)    res += x * abs(t.query(1, r + 1) - t.query(1, r));
        t.update(l, k), t.update(r + 1, -k);
        if(l > 1 and t.query(1, l) <= t.query(1, l - 1))    res += y * abs(t.query(1, l) - t.query(1, l - 1));
        else if(l > 1)   res -= x * abs(t.query(1, l) - t.query(1, l - 1));
        if(r < n + 1 and t.query(1, r + 1) <= t.query(1, r))    res += y * abs(t.query(1, r + 1) - t.query(1, r));
        else if(r < n + 1) res -= x * abs(t.query(1, r + 1) - t.query(1, r));
        cout << res << endl;
    }
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 600 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 5 ms 452 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 5 ms 544 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 452 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 6 ms 348 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Correct 4 ms 348 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 4 ms 348 KB Output is correct
18 Correct 4 ms 452 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 600 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 473 ms 10172 KB Output is correct
2 Correct 460 ms 11088 KB Output is correct
3 Correct 460 ms 11544 KB Output is correct
4 Correct 464 ms 10968 KB Output is correct
5 Correct 525 ms 12208 KB Output is correct
6 Correct 409 ms 11092 KB Output is correct
7 Correct 410 ms 11008 KB Output is correct
8 Correct 472 ms 11940 KB Output is correct
9 Correct 446 ms 12144 KB Output is correct
10 Correct 466 ms 11024 KB Output is correct
11 Correct 405 ms 10968 KB Output is correct
12 Correct 414 ms 11648 KB Output is correct
13 Correct 431 ms 12080 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 600 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 5 ms 452 KB Output is correct
4 Correct 5 ms 344 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 5 ms 544 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 452 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 5 ms 344 KB Output is correct
12 Correct 6 ms 348 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Correct 4 ms 348 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 4 ms 348 KB Output is correct
18 Correct 4 ms 452 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 600 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 473 ms 10172 KB Output is correct
23 Correct 460 ms 11088 KB Output is correct
24 Correct 460 ms 11544 KB Output is correct
25 Correct 464 ms 10968 KB Output is correct
26 Correct 525 ms 12208 KB Output is correct
27 Correct 409 ms 11092 KB Output is correct
28 Correct 410 ms 11008 KB Output is correct
29 Correct 472 ms 11940 KB Output is correct
30 Correct 446 ms 12144 KB Output is correct
31 Correct 466 ms 11024 KB Output is correct
32 Correct 405 ms 10968 KB Output is correct
33 Correct 414 ms 11648 KB Output is correct
34 Correct 431 ms 12080 KB Output is correct
35 Correct 502 ms 10324 KB Output is correct
36 Correct 508 ms 11844 KB Output is correct
37 Correct 470 ms 12564 KB Output is correct
38 Correct 465 ms 12556 KB Output is correct
39 Correct 543 ms 12360 KB Output is correct
40 Correct 476 ms 12652 KB Output is correct
41 Correct 478 ms 12420 KB Output is correct
42 Correct 461 ms 12272 KB Output is correct
43 Correct 460 ms 11624 KB Output is correct
44 Correct 471 ms 11988 KB Output is correct
45 Correct 455 ms 11976 KB Output is correct
46 Correct 498 ms 13084 KB Output is correct
47 Correct 435 ms 11864 KB Output is correct
48 Correct 439 ms 11612 KB Output is correct
49 Correct 456 ms 10772 KB Output is correct
50 Correct 422 ms 11704 KB Output is correct
51 Correct 411 ms 11856 KB Output is correct
52 Correct 410 ms 11604 KB Output is correct