Submission #261506

#	Time	Username	Problem	Language	Result	Execution time	Memory
261506		jainbot27	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	224 ms	13560 KiB

foehn_phenomena

//Created on: 08.11.20
#pragma GCC optimize ("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
using namespace std;


#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ts to_string
#define ub upper_bound
#define lb lower_bound
#define ar array
#define FOR(x, y, z) for(int x = y; x < z; x++)
#define ROF(x, y, z) for(int x = y; x > z; x--)
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()


const char nl = '\n';
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using vpii = vector<pii>;
using vpll = vector<pll>;


template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


str ts(char c) { return str(1,c); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
template<class A> str ts(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) { 
    str res = "{"; for(int i = 0;i < (int)v.size(); i++) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
    str res = ""; for(int i = 0; i < b.size(); i++) res += char('0'+b[i]);
    return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { 
    bool fst = 1; str res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += ts(x);
    }
    res += "}"; return res;
}
template<class A, class B> str ts(pair<A,B> p) {
    return "("+ts(p.f)+", "+ts(p.s)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << ts(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }


#ifdef D 
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
#define int long long
typedef ll node;
struct BIT{
    //ask for queries 0 idxed or remove ++idx/++r
    vector<node> bit;
    int n;
    void init(int x){
        n=x+1;
        bit.assign(n + 1,0LL);
    }
    ll sum(int r){
        ll ret = 0;
        for(r++; r ; r -= r & -r){
            ret += bit[r];
        }
        return ret;
    }
    ll sum(int l, int r){
        return sum(r) - sum(l-1);
    }
    void add(int idx, int delta){
        for(idx++; idx < n; idx += idx & -idx){
            bit[idx] += delta;
        }
    }
}bit;
ll n, qq, s, t, val[200010];
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> qq >> s >> t;
    bit.init(n+10);
    for(int i=0; i  < n+1; i++){
        cin >> val[i];
        bit.add(i, val[i]);
        bit.add(i+1, -val[i]);
    }
    int sum = 0;
    for(int i = 1;i < n +1; i++){
        if(val[i] > val[i-1])
            sum -= s * (abs(val[i] - val[i-1]));
        else
            sum+= t * (abs(val[i] - val[i-1]));
        dbg(sum);
    }
    dbg(sum);
    while(qq--){
        int l, r, q;
        cin >> l >> r >> q;
        ll w = bit.sum(0, l);
        ll e = bit.sum(0,l-1);
        if(w > e)
            sum += (w-e) * s;
        else
            sum -= (e-w) * t;
        dbg(w, e, sum);
        e = bit.sum(0, r);
        w = bit.sum(0,r+1);
        if(r != n){
            if(w > e)
                sum += (w-e) * s;
            else
                sum -= (e-w) * t;
        }
        dbg(w, e,sum);
        bit.add(l, q);
        bit.add(r + 1, -q);
        w = bit.sum(0, l);
        e = bit.sum(0,l-1);
        dbg(w, e);
        if(w > e)
            sum -= (w-e) * s;
        else
            sum += (e-w) * t;
        e = bit.sum(0, r);
        w = bit.sum(0,r+1);
        dbg(w, e);
        if(r != n){
            if(w > e)
                sum -= (w-e) * s;
            else 
                sum += (e-w) * t;
        }
        cout << sum << nl; 
    }
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:114:17: warning: statement has no effect [-Wunused-value]
         dbg(sum);
                 ^
foehn_phenomena.cpp:116:13: warning: statement has no effect [-Wunused-value]
     dbg(sum);
             ^
foehn_phenomena.cpp:126:23: warning: statement has no effect [-Wunused-value]
         dbg(w, e, sum);
                       ^
foehn_phenomena.cpp:135:22: warning: statement has no effect [-Wunused-value]
         dbg(w, e,sum);
                      ^
foehn_phenomena.cpp:140:18: warning: statement has no effect [-Wunused-value]
         dbg(w, e);
                  ^
foehn_phenomena.cpp:147:18: warning: statement has no effect [-Wunused-value]
         dbg(w, e);
                  ^

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