Submission #219730

#	Time	Username	Problem	Language	Result	Execution time	Memory
219730		MKopchev	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	209 ms	12408 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
const int nmax=2e5+42;
int n,q,s,t;

long long fenwick[nmax];

void update(int pos,int val)
{
    while(pos<=n)
    {
        fenwick[pos]+=val;
        pos=pos+(pos&(-pos));
    }
}
void upd(int l,int r,int val)
{
    update(l,val);
    update(r+1,-val);
}

long long query(int pos)
{
    long long ret=0;
    while(pos)
    {
        ret=ret+fenwick[pos];
        pos=pos-(pos&(-pos));
    }
    return ret;
}
long long score(int pos)
{
    if(pos==n)return 0;

    long long was=query(pos),is=query(pos+1);
    if(was<is)return (was-is)*s;
    return (was-is)*t;
}

int inp[nmax];
int main()
{
    scanf("%i%i%i%i",&n,&q,&s,&t);

    for(int i=0;i<=n;i++)
    {
        scanf("%i",&inp[i]);
        if(i)upd(i,i,inp[i]);
    }

    long long ret=0;
    for(int i=0;i<n;i++)
        ret=ret+score(i);

    for(int i=1;i<=q;i++)
    {
        int l,r,x;
        scanf("%i%i%i",&l,&r,&x);

        ret=ret-score(l-1)-score(r);
        upd(l,r,x);

        ret=ret+score(l-1)+score(r);
        printf("%lld\n",ret);
    }
    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i%i%i",&n,&q,&s,&t);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&inp[i]);
         ~~~~~^~~~~~~~~~~~~~
foehn_phenomena.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i%i",&l,&r,&x);
         ~~~~~^~~~~~~~~~~~~~~~~~~

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