Submission #170641

#	Time	Username	Problem	Language	Result	Execution time	Memory
170641		mdn2002	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	0 / 100	1078 ms	5944 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n,q,s,t,tree[800005],lazy[800005],ans;
void up(int nod,int l,int r,int x,int y,int val)
{
    if(lazy[nod]!=0)
    {
        tree[nod]+=lazy[nod];
        if(l!=r)
        {
            lazy[nod*2]+=lazy[nod];
            lazy[nod*2+1]+=lazy[nod];
        }
        lazy[nod]=0;
    }
    if(r<x||y<l)return;
    if(x<=l&&r<=y)
    {
        tree[nod]+=val;
        if(l!=r)
        {
            lazy[nod*2]+=val;
            lazy[nod*2+1]+=val;
        }
        return;
    }
    int mid=(l+r)/2;
    up(nod*2,l,mid,x,y,val);
    up(nod*2+1,mid+1,r,x,y,val);
    tree[nod]=tree[nod*2]+tree[nod*2+1];
}
int qu(int nod,int l,int r,int x)
{
    if(lazy[nod]!=0)
    {
        tree[nod]+=lazy[nod];
        if(l!=r)
        {
            lazy[nod*2]+=lazy[nod];
            lazy[nod*2+1]+=lazy[nod];
        }
        lazy[nod]=0;
    }
    if(x<l||r<x)return 0;
    if(l==r)return tree[nod];
    int mid=(l+r)/2;
    return qu(nod*2,l,mid,x)+qu(nod*2+1,mid+1,r,x);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>q>>s>>t;
    int b;
    cin>>b;
    up(1,0,n,0,0,b);
    for(int i=0;i<n;i++)
    {
        int a;
        cin>>a;
        int dif=b-a;
        if(dif>=0)ans+=dif*t;
        else ans+=dif*s;
        up(1,0,n,i+1,i+1,a);
        b=a;
    }
    while(q--)
    {
        int l,r,x;
        cin>>l>>r>>x;
        int oa=qu(1,0,n,l);
        int ob=qu(1,0,n,r);
        up(1,0,n,l,r,x);
        int a=qu(1,0,n,l);
        int b=qu(1,0,n,r);
        int c=qu(1,0,n,l-1);
        int d=qu(1,0,n,r+1);
        if(l>0)
        {
            int dif=c-oa;
            if(dif>=0)ans-=dif*t;
            else ans-=dif*s;
            dif=c-a;
            if(dif>=0)ans+=dif*t;
            else ans+=dif*s;
        }
        if(r<n)
        {
            int dif=ob-d;
            if(dif>=0)ans-=dif*t;
            else ans-=dif*s;
            dif=b-d;
            if(dif>=0)ans+=dif*t;
            else ans+=dif*s;
        }
        cout<<ans<<endl;
    }
}

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