Submission #438868

#TimeUsernameProblemLanguageResultExecution timeMemory
438868SnowfallFoehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
753 ms19740 KiB
#include<bits/stdc++.h>
using namespace std;
long long seg[800005],seg2[800005];
long long arr[200005];
long long a,b;
void up(int st,int ed,int lv,int po,long long val,long long pval)
{
    if(st>po || ed<po)
    return;
    if(st==po && ed==po)
    {
        if(val>pval)
        seg[lv]=-a*(val-pval);
        else
        seg[lv]=-b*(val-pval);
        return;
    }
    int md=(st+ed)/2;
    int lv2=lv*2;
    up(st,md,lv2,po,val,pval);
    up(md+1,ed,lv2+1,po,val,pval);
    seg[lv]=seg[lv2]+seg[lv2+1];
}
void upseg2(int st,int ed,int lv,int l,int r,long long val)
{
    if(st>r || ed<l)
    return;
    if(st>=l && ed<=r)
    {
        seg2[lv]+=val;
        return;
    }
    int md=(st+ed)/2;
    int lv2=lv*2;
    upseg2(st,md,lv2,l,r,val);
    upseg2(md+1,ed,lv2+1,l,r,val);
}
long long get_val(int st,int ed,int lv,int po,long long val)
{
    if(st>po || ed<po)
    return 0;
    if(st==po && ed==po)
    {
        return val+seg2[lv];
    }
    int md=(st+ed)/2;
    int lv2=lv*2;
    long long tval=val+seg2[lv];
    return get_val(st,md,lv2,po,tval)+get_val(md+1,ed,lv2+1,po,tval);
}
main()
{
	int t,q;
    scanf("%d%d%lld%lld",&t,&q,&a,&b);
    for(int i = 0;i <= t;i++)
    {
        scanf("%lld",&arr[i]);
        if(i==0)
        continue;
        up(0,t,1,i,arr[i],arr[i-1]);
        upseg2(0,t,1,i,i,arr[i]);
    }
    int l,r;
    long long v;
    for(int i = 0;i < q;i++)
    {
        scanf("%d%d%lld",&l,&r,&v);
        upseg2(0,t,1,l,r,v);
        long long l1=get_val(0,t,1,l-1,0),l2=get_val(0,t,1,l,0);
        up(0,t,1,l,l2,l1);
        if(r<=t-1)
        {
            long long r1=get_val(0,t,1,r,0),r2=get_val(0,t,1,r+1,0);
            up(0,t,1,r+1,r2,r1);
        }
        printf("%lld\n",seg[1]);
    }
}

Compilation message (stderr)

foehn_phenomena.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main()
      | ^~~~
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d%d%lld%lld",&t,&q,&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%lld",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
foehn_phenomena.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d%d%lld",&l,&r,&v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...