Submission #536191

#	Time	Username	Problem	Language	Result	Execution time	Memory
536191		groshi	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	212 ms	14688 KiB

foehn_phenomena

#include<iostream>

using namespace std;
int pot=1;
long long drzewo[500000];
long long a[300000];
void dodaj(int x,int y,long long ile)
{
    x+=pot;
    y+=pot;
    drzewo[x]+=ile;
    if(x!=y)
        drzewo[y]+=ile;
    while(x/2!=y/2)
    {
        if(x%2==0)
            drzewo[x+1]+=ile;
        if(y%2==1)
            drzewo[y-1]+=ile;
        x/=2;
        y/=2;
    }
}
long long zap(int x)
{
    x+=pot;
    long long wynik=0;
    wynik+=drzewo[x];
    x/=2;
    while(x>0)
    {
        wynik+=drzewo[x];
        x/=2;
    }
    return wynik;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    long long n,q,s,t,x,y,z;
    cin>>n>>q>>s>>t;
    for(int i=1;i<=n+1;i++)
        cin>>a[i];
    while(pot<=n)
        pot*=2;
    pot--;
    for(int i=1;i<=n+1;i++)
        drzewo[i+pot]=a[i];
    long long wynik=0;
    for(int i=2;i<=n+1;i++)
    {
        if(a[i]>a[i-1])
            wynik-=(a[i]-a[i-1])*s;
        else wynik+=(a[i-1]-a[i])*t;
    }
    while(q--)
    {
        cin>>x>>y>>z;
        x++;
        y++;
        dodaj(x,y,z);
        long long nowy_x=zap(x);
        long long nowy_y=zap(y);
        //if(x>1)
        //{
            long long x_1=zap(x-1);
            long long stary_x=nowy_x-z;
            if(stary_x>x_1)
                wynik+=(stary_x-x_1)*s;
            else wynik-=(x_1-stary_x)*t;
            if(nowy_x>x_1)
                wynik-=(nowy_x-x_1)*s;
            else wynik+=(x_1-nowy_x)*t;
        //}
        if(y<n+1)
        {
            long long y_1=zap(y+1);
            long long stary_y=nowy_y-z;
            if(y_1>stary_y)
                wynik+=(y_1-stary_y)*s;
            else wynik-=(stary_y-y_1)*t;
            if(y_1>nowy_y)
                wynik-=(y_1-nowy_y)*s;
            else wynik+=(nowy_y-y_1)*t;
        }
        cout<<wynik<<"\n";
    }
    return 0;
}

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