제출 #1269795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269795		k12_khoi	Foehn Phenomena (JOI17_foehn_phenomena)	C++17	100 / 100	101 ms	7880 KiB

foehn_phenomena

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

#define ll long long

const int N=2e5+5;

int n,request; ll S,T,x,y,res;

namespace sub1
{
    int l,r,x;
    ll a[N];

    void solve()
    {
        for (int i=0;i<=n;i++)
        cin >> a[i];

        a[0]=0;
        while (request--)
        {
            cin >> l >> r >> x;

            for (int i=l;i<=r;i++)
            a[i]+=x;

            res=0;
            for (int i=0;i<n;i++)
            {
                if (a[i]<a[i+1]) res-=S*(a[i+1]-a[i]);
                else res+=T*(a[i]-a[i+1]);
            }

            cout << res << '\n';
        }
    }
}

namespace sub3
{
    int l,r,z;
    ll bit[N];

    void updateBit(int u,int v)
    {
        for (int idx=u;idx<=n;idx+=idx&-idx)
        bit[idx]+=v;
    }

    ll get(int u)
    {
        ll ans=0;
        for (int idx=u;idx>0;idx-=idx&-idx)
        ans+=bit[idx];

        return ans;
    }

    void updateRange(int l,int r,int v)
    {
        updateBit(l,v);
        updateBit(r+1,-v);
    }

    void solve()
    {
        cin >> x;

        res=0;
        y=0;
        for (int i=1;i<=n;i++)
        {
            cin >> x;
            updateRange(i,i,x);

            if (y<x) res+=(y-x)*S;
            else res+=(y-x)*T;

            y=x;
        }

        while (request--)
        {
            cin >> l >> r >> z;

            x=get(l-1);
            y=get(l);
            if (x<y) res-=(x-y)*S;
            else res-=(x-y)*T;

            y+=z;
            if (x<y) res+=(x-y)*S;
            else res+=(x-y)*T;


            if (r!=n)
            {
                x=get(r);
                y=get(r+1);
                if (x<y) res-=(x-y)*S;
                else res-=(x-y)*T;

                x+=z;
                if (x<y) res+=(x-y)*S;
                else res+=(x-y)*T;
            }

            updateRange(l,r,z);

            cout << res << '\n';
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> request >> S >> T;

    sub3::solve();
}

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