제출 #332027

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
332027		FatihSolak	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	198 ms	8076 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl "\n"
#define all(x) (x).begin(), (x).end()
using namespace std;
const int INF = (int) 1e9;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
struct FenwickTreeOneBasedIndexing {
    vector<ll> bit;  // binary indexed tree
    ll n;

    FenwickTreeOneBasedIndexing(ll n) {
        this->n = n + 1;
        bit.assign(n + 1, 0);
    }

    FenwickTreeOneBasedIndexing(vector<ll> a)
        : FenwickTreeOneBasedIndexing(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            range_add(i,i, a[i]);
    }

    ll sum(ll idx) {
        ll ret = 0;
        for (++idx; idx > 0; idx -= idx & -idx)
            ret += bit[idx];
        return ret;
    }

    ll sum(ll l, ll r) {
        return sum(r) - sum(l - 1);
    }

    void add(ll idx, ll delta) {
        for (++idx; idx < n; idx += idx & -idx)
            bit[idx] += delta;
    }
    void range_add(ll l, ll r, ll val) {
        add(l, val);
        add(r + 1, -val);
    }
    ll point_query(ll idx) {
        ll ret = 0;
        for (++idx; idx > 0; idx -= idx & -idx)
            ret += bit[idx];
        return ret;
    }
};
ll n,q,s,t;
ll calc(ll a, ll b){
    if(a < b){
        return -(s*(b-a));
    }
    else{
        return t*(a-b);
    }
}
void solve(){
    cin >> n >> q >> s >> t;
    vector<ll> a(n+1);
    for(ll i=0;i<=n;i++){
        cin >> a[i];
    }
    ll ans = 0;
    for(int i=0;i<n;i++){
        ans += calc(a[i],a[i+1]);
    }
    FenwickTreeOneBasedIndexing bt(a);
    //cout << ans << endl;
    while(q--){
        ll l,r,val;
        cin >> l >> r >> val;
        ll nowl = bt.point_query(l);
        ll nowr = bt.point_query(r);
        ll nowll = bt.point_query(l-1);
        ll nowrr = bt.point_query(min(n,r+1));
        ll now_suml = calc(nowll,nowl);
        ll now_sumr = calc(nowr,nowrr);
        bt.range_add(l,r,val);
        ll posl = bt.point_query(l);
        ll posr = bt.point_query(r);
        ll posll = bt.point_query(l-1);
        //cout << posll << " " << posl << endl;
        ans += calc(posll,posl) - now_suml;
        //cout << ans << endl;
        if(r!=n){
            ll posrr = bt.point_query(r+1);
            //cout << posr << " " << posrr << endl;
            ans += calc(posr,posrr) - now_sumr;
        }
        cout << ans << endl;
        //break;
    }

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

• Subtask 1: 30 / 30
• Subtask 2: 10 / 10
• Subtask 3: 60 / 60