oj.uz

Submission #951145

# Submission time Handle Problem Language Result Execution time Memory
951145 2024-03-21T08:46:19 Z tnknguyen_ Foehn Phenomena (JOI17_foehn_phenomena) C++14
10 / 100
 111 ms 19504 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n' 

const int sz = 2e5 + 5;
vector<int> qr[sz];
long long a[sz], d[sz];
int n, q, s, t;

// ------------ FUNCTIONS -----------
struct BIT{
    vector<int> f;
    int n = 2e5 + 5;

    BIT(){
        f.assign(n, 0);
    }

    void update(int i, int val){
        while(i < n){
            f[i] += val;
            i += (i & -i);
        }
    }

    int get(int i){
        int ans = 0;
        while(i > 0){
            ans += f[i];
            i -= (i & -i);
        }
        return ans;
    }
};

int cost(int x, int y){
    return (y > x ? -s*(y - x) : t*(x - y));
}

// ------------ SUBTASKS ------------
namespace SUB1{
    bool ok(){
        return (n <= 2000 && q <= 2000);
    }

    void solve(){
        for(int i=1; i<=q; ++i){
            int l = qr[i][0], r = qr[i][1], x = qr[i][2];
            int ans = 0;
            for(int j=1; j<=n; ++j){
                if(j >= l && j <= r){
                    a[j] += x;
                }
                if(a[j-1] < a[j]){
                    ans -= (a[j] - a[j-1])*s;
                }
                else{
                    ans += (a[j-1] - a[j])*t;
                }
            }
            cout<<ans<<endl;
        }
    }
}

namespace SUB23{
    void solve(){
        BIT bit;
        int ans = 0;
        for(int i=1; i<=n; ++i){
            bit.update(i, a[i]);
            bit.update(i+1, -a[i]);
            ans += cost(a[i-1], a[i]);
        }

        for(int i=1; i<=q; ++i){
            int l = qr[i][0], r = qr[i][1], x = qr[i][2];

            ans -= cost(bit.get(l-1), bit.get(l));
            bit.update(l, x);
            ans += cost(bit.get(l-1), bit.get(l));

            if(r + 1 <= n){
                ans -= cost(bit.get(r), bit.get(r+1));
                bit.update(r+1, -x);
                ans += cost(bit.get(r), bit.get(r+1));
            }

            cout<<ans<<endl;
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //freopen("main.inp","r",stdin);
    //freopen("main.out","w",stdout);

    cin>>n>>q>>s>>t;
    for(int i=0; i<=n; ++i){
        cin>>a[i];
    }
    
    for(int i=1; i<=q; ++i){
        int l, r, x;
        cin>>l>>r>>x;
        qr[i] = {l, r, x};
    }

    if(SUB1::ok()){
        SUB1::solve();
    }
    SUB23::solve();

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 17156 KB Output is correct
2 Correct 104 ms 17820 KB Output is correct
3 Correct 108 ms 18412 KB Output is correct
4 Correct 99 ms 17488 KB Output is correct
5 Correct 111 ms 18256 KB Output is correct
6 Correct 76 ms 18772 KB Output is correct
7 Correct 77 ms 18772 KB Output is correct
8 Correct 99 ms 18768 KB Output is correct
9 Correct 103 ms 19088 KB Output is correct
10 Correct 98 ms 17748 KB Output is correct
11 Correct 81 ms 18768 KB Output is correct
12 Correct 91 ms 19288 KB Output is correct
13 Correct 76 ms 19504 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 9560 KB Output isn't correct
2 Halted 0 ms 0 KB -