Submission #535501

#	Time	Username	Problem	Language	Result	Execution time	Memory
535501		hibiki	Foehn Phenomena (JOI17_foehn_phenomena)	C++11	100 / 100	469 ms	24032 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;

long long n,q,s,t;
long long a[200200];
long long base=0;

struct NODE
{
    long long add=0;
    NODE *l=NULL,*r=NULL;
} *root;

NODE* build(int l,int r)
{
    NODE *ptr = new NODE;
    if(l==r)
    {
        ptr->add=a[l];
        return ptr;
    }
    int mid=(l+r)/2;
    ptr->l=build(l,mid);
    ptr->r=build(mid+1,r);
    return ptr;
}

long long val;
int ll,rr;
void update(NODE *ptr,int l,int r)
{
    if(ll<=l&&r<=rr)
    {
        ptr->add+=val;
        return ;
    }
    else if(r<ll||rr<l)
        return ;
    int mid=(l+r)/2;
    update(ptr->l,l,mid);
    update(ptr->r,mid+1,r);
    return ;
}

int po;
long long query(NODE *ptr,int l,int r)
{
    if(l==r)
        return ptr->add;
    int mid=(l+r)/2;
    if(po<=mid)
        return ptr->add+query(ptr->l,l,mid);
    else
        return ptr->add+query(ptr->r,mid+1,r);
}

main()
{
    scanf("%lld %lld %lld %lld",&n,&q,&s,&t);
    for(int i=0;i<n+1;i++)
    {
        scanf("%lld",&a[i]);
        if(i)
        {
            if(a[i-1]<a[i])
                base-=s*(a[i]-a[i-1]);
            else
                base+=t*(a[i-1]-a[i]);
        }
    }
    root=build(0,n);
    //printf("%lld\n",base);
    for(int i=0;i<q;i++)
    {
        long long l,r,x;
        scanf("%lld %lld %lld",&l,&r,&x);
        long long cha=0;
        po=l-1;
        long long prell=query(root,0,n);
        po=l;
        long long prel=query(root,0,n);
        //printf("-%lld %lld-\n",prell,prel);
        if(prell<prel)
            cha-=s*(prel-prell);
        else
            cha+=t*(prell-prel);
        if(r!=n)
        {
            po=r+1;
            long long prerr=query(root,0,n);
            po=r;
            long long prer=query(root,0,n);
            //printf("-%lld %lld-\n",prer,prerr);
            if(prer<prerr)
                cha-=s*(prerr-prer);
            else
                cha+=t*(prer-prerr);
        }
        cha*=-1;
        ll=l;
        rr=r;
        val=x;
        update(root,0,n);
        po=l-1;
        long long postll=query(root,0,n);
        po=l;
        long long postl=query(root,0,n);
        //printf("-%lld %lld-\n",postll,postl);
        if(postll<postl)
            cha-=s*(postl-postll);
        else
            cha+=t*(postll-postl);
        if(r!=n)
        {
            po=r+1;
            long long postrr=query(root,0,n);
            po=r;
            long long postr=query(root,0,n);
            //printf("-%lld %lld-\n",postr,postrr);
            if(postr<postrr)
                cha-=s*(postrr-postr);
            else
                cha+=t*(postr-postrr);
        }
        base+=cha;
        printf("%lld\n",base);
    }
}

Compilation message (stderr)

foehn_phenomena.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 | main()
      | ^~~~
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%lld %lld %lld %lld",&n,&q,&s,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~
foehn_phenomena.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         scanf("%lld %lld %lld",&l,&r,&x);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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