Submission #267320

#	Time	Username	Problem	Language	Result	Execution time	Memory
267320		leductoan	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	555 ms	20076 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
#define task "Phenomena"
#define lb lower_bound
#define ub upper_bound
#define alll(v) (v).begin(),(v).end()
#define szz(v) (v).size()
#define fi first
#define se second
#define pb push_back
#define FOR(i,a,b) for (ll i = (a), _b = (b); i <= _b; ++i)
#define FORD(i,b,a) for (ll i = (b), _a = (a); i >= _a; --i)
typedef long double ld;
typedef long long ll;
typedef pair<ll,ll> pii;

template <typename T>
inline void read(T& x)
{
    bool Neg = false;
    char c;
    for (c = getchar(); c < '0' | c > '9'; c = getchar())
        if (c == '-') Neg = !Neg;
    x = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    if (Neg) x = -x;
}

template <typename T>
inline void write(T x)
{
    if (x < 0)
    {
        putchar('-'); x = -x;
    }
    T p = 1;
    for (T temp = x / 10; temp > 0; temp /= 10) p *= 10;
    for (; p > 0; x %= p, p /= 10) putchar(x / p + '0');
}
const ll MOD=1000000007; /// 998244353
const ll base=311; /// for hash actually
const ll N=2e5+5;

ll st[4*N],lazy[4*N],n,q,s,t,a[N];
void down(ll i, ll l, ll r)
{
    ll t=lazy[i];
    st[i<<1]+=t;
    st[i<<1|1]+=t;
    lazy[i<<1]+=t;
    lazy[i<<1|1]+=t;
    lazy[i]=0;
}
void upd(ll i, ll l, ll r, ll u, ll v, ll val)
{
    if(u>r||v<l) return;
    if(u<=l&&r<=v)
    {
        lazy[i]+=val;
        st[i]+=val;
        return;
    }
    down(i,l,r);
    ll mid=(l+r)>>1;
    upd(i<<1,l,mid,u,v,val);
    upd(i<<1|1,mid+1,r,u,v,val);
}
ll get(ll i, ll l, ll r, ll p)
{
    if(l==r) return st[i];
    down(i,l,r);
    ll mid=(l+r)>>1;
    if(p<=mid) return get(i<<1,l,mid,p);
    else return get(i<<1|1,mid+1,r,p);
}
void solved()
{
    read(n); read(q); read(s); read(t);
    s=-s;
    ll ans=0;
    ++n;
    FOR(i,1,n)
    {
        read(a[i]);
        upd(1,1,n,i,i,a[i]);
    }
    FOR(i,1,n-1)
    {
        if(a[i]<a[i+1]) ans+=s*(a[i+1]-a[i]);
        else ans+=t*(a[i]-a[i+1]);
    }
    while(q--)
    {
        ll l,r,x;
        read(l); read(r); read(x);
        ++l,++r;
        if(l>1)
        {
            ll p1=get(1,1,n,l-1), p2=get(1,1,n,l);
            if(p1<p2) ans-=s*(p2-p1);
            else ans-=t*(p1-p2);
        }
        if(r<n)
        {
            ll p1=get(1,1,n,r), p2=get(1,1,n,r+1);
            if(p1<p2)ans-=s*(p2-p1);
            else ans-=t*(p1-p2);
        }
        upd(1,1,n,l,r,x);
        if(l>1)
        {
            ll p1=get(1,1,n,l-1), p2=get(1,1,n,l);
            if(p1<p2) ans+=s*(p2-p1);
            else ans+=t*(p1-p2);
        }
        if(r<n)
        {
            ll p1=get(1,1,n,r), p2=get(1,1,n,r+1);
            if(p1<p2)ans+=s*(p2-p1);
            else ans+=t*(p1-p2);
        }
        write(ans); putchar('\n');
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    solved();
}

Compilation message (stderr)

foehn_phenomena.cpp: In instantiation of 'void read(T&) [with T = long long int]':
foehn_phenomena.cpp:79:11:   required from here
foehn_phenomena.cpp:22:27: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   22 |     for (c = getchar(); c < '0' | c > '9'; c = getchar())
      |                         ~~^~~~~
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  131 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  132 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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