Submission #1158845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158845		qin	Foehn Phenomena (JOI17_foehn_phenomena)	C++20	100 / 100	121 ms	9808 KiB

foehn_phenomena

#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#endif
#include <bits/stdc++.h>
#define fi first
#define se second
#define pn printf("\n")
#define ssize(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define bitcount(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define mp make_pair
//~ #define r(x) resize(x)
//~ #define rf(x, c) resize(x, c)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
#define V vector
int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1;
int add(int a, int b){return a+b >= mod ? a+b - mod : a+b;}
int sub(int a, int b){return a-b < 0 ? a-b + mod : a-b;}
int mul(int a, int b){return int(a * ll(b) % mod);}
int fpow(int a, ll b){
    int ret = 1;
    while(b){
        if(b & 1) ret = mul(ret, a);
        b >>= 1, a = mul(a, a);
    } return ret;
}
int inv(int a){ return fpow(a, mod-2); }
struct coeff{
    V<int> fac, invfac;
    coeff(int n){
        fac.resize(n+1), invfac.resize(n+1);
        fac[0] = 1, invfac[0] = 1;
        for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i-1], i);
        invfac[n] = inv(fac[n]);
        for(int i = n-1; i; --i) invfac[i] = mul(invfac[i+1], i+1);
    }
    int get(int n, int k){
        if(n < k) return 0;
        return mul(fac[n], mul(invfac[n-k], invfac[k]));
    }
};
struct seg{
    int base = 1;
    V<ll> t;
    seg(int n, V<ll> &a){
        while(base < n) base <<= 1;
        t.resize(base<<1, 0);
        for(int i = 1; i <= n; ++i) t[i+base-1] = a[i];
    }
    void update(int l, int r, ll val){
        for(l += base-1, r += base; l < r; l >>= 1, r >>= 1){
            if(l&1) t[l++] += val;
            if(r&1) t[--r] += val;
        }
    }
    ll query(int i){
        ll ret = 0;
        for(i += base-1; i; i >>= 1) ret += t[i];
        return ret;
    }
};

void answer(){
	int n, q; ll S, T; scanf("%d%d%lld%lld", &n, &q, &S, &T);
    V<ll> t(n+1, 0);
    for(int i = 0; i <= n; ++i) scanf("%lld", &t[i]);
    seg seg(n, t);

    ll result = 0;
    function<ll(int)> move = [&](int i){
        if(i == n) return 0ll;
        if(!i){
            ll b = seg.query(1);
            return 0 < b ?  b*(-S) : -b*T;
        }
        ll a = seg.query(i), b = seg.query(i+1);
        return a < b ? -S*(b-a) : T*(a-b);
    };
    for(int i = 0; i <= n; ++i) result += move(i);

    // printf("%lld\n", result);

    for(++q; --q; ){
        int l, r; ll val; scanf("%d%d%lld", &l, &r, &val);
        result -= move(l-1), result -= move(r);
        seg.update(l, r, val);
        result += move(l-1), result += move(r);
        printf("%lld\n", result);
    }
}
int main(){
		int T = 1;
		// scanf("%d", &T);
		//~ ios_base::sync_with_stdio(0); cin.tie(0); cin >> T;
		for(++T; --T; ) answer();
		return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void answer()':
foehn_phenomena.cpp:74:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         int n, q; ll S, T; scanf("%d%d%lld%lld", &n, &q, &S, &T);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:76:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     for(int i = 0; i <= n; ++i) scanf("%lld", &t[i]);
      |                                 ~~~~~^~~~~~~~~~~~~~~
foehn_phenomena.cpp:94:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         int l, r; ll val; scanf("%d%d%lld", &l, &r, &val);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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