Submission #321632

#	Time	Username	Problem	Language	Result	Execution time	Memory
321632		daniel920712	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	731 ms	27372 KiB

foehn_phenomena

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
long long all[200005],now=1;
struct A
{
    long long l,r;
    long long nxl,nxr;
    long long add;
}Node[2000005];
void build(long long l,long long r,long long here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].add=0;
    if(l==r)
    {
        Node[here].add=all[l];
        return;
    }
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
}
long long Find(long long where,long long here)
{
    if(Node[here].l==where&&Node[here].r==where) return Node[here].add;
    if(where<=(Node[here].l+Node[here].r)/2) return Find(where,Node[here].nxl)+Node[here].add;
    else return Find(where,Node[here].nxr)+Node[here].add;
}
void add(long long l,long long r,long long con,long long here)
{
    if(l==Node[here].l&&r==Node[here].r)
    {
        Node[here].add+=con;
        return;
    }
    if(r<=(Node[here].l+Node[here].r)/2) add(l,r,con,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) add(l,r,con,Node[here].nxr);
    else
    {
        add(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
        add((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
    }
}
int main()
{
    long long N,M,S,T,l,r,x,y,tt=0,con,i;
    scanf("%lld %lld %lld %lld",&N,&M,&S,&T);
    for(i=0;i<=N;i++)
    {
        scanf("%lld",&all[i]);
        if(i&&all[i-1]<all[i]) tt-=abs(all[i]-all[i-1])*S;
        if(i&&all[i-1]>=all[i]) tt+=abs(all[i]-all[i-1])*T;
    }
    build(0,N,0);
    //printf("%lld\n",tt);
    while(M--)
    {
        scanf("%lld %lld %lld",&l,&r,&con);
        x=Find(l,0);
        y=Find(l-1,0);
        if(y<x) tt+=abs(x-y)*S;
        if(y>=x) tt-=abs(x-y)*T;

        if(r!=N)
        {
            x=Find(r+1,0);
            y=Find(r,0);
            if(y<x) tt+=abs(x-y)*S;
            if(y>=x) tt-=abs(x-y)*T;
            //printf("%lld %lld\n",x,y);
        }



        add(l,r,con,0);

        x=Find(l,0);
        y=Find(l-1,0);
        if(y<x) tt-=abs(x-y)*S;
        if(y>=x) tt+=abs(x-y)*T;

         if(r!=N)
        {
            x=Find(r+1,0);
            y=Find(r,0);
            if(y<x) tt-=abs(x-y)*S;
            if(y>=x) tt+=abs(x-y)*T;
            //printf("%lld %lld\n",x,y);
        }

        printf("%lld\n",tt);


    }
    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     scanf("%lld %lld %lld %lld",&N,&M,&S,&T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |         scanf("%lld",&all[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
foehn_phenomena.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |         scanf("%lld %lld %lld",&l,&r,&con);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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