Submission #997334

#	Time	Username	Problem	Language	Result	Execution time	Memory
997334		Malix	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	629 ms	18740 KiB

foehn_phenomena

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

vector<ll> a,b;

void update(int l,int r,int k,int x,int y,int z){
    if(x>y)return;
    //cout<<l<<" "<<r<<" "<<x<<" "<<y<<"\n";
    if(l==x&&r==y)b[k]+=z;
    else{
        int m=(l+r)/2;
        update(l,m,k*2,x,min(m,y),z);
        update(m+1,r,k*2+1,max(x,m+1),y,z);
    }
}

ll find(int l,int r,int k,ll v){
    if(l==r)return a[v]+b[k];
    int m=(l+r)/2;
    if(v>m)return b[k]+find(m+1,r,k*2+1,v);
    else return b[k]+find(l,m,k*2,v);
}

int main() {   
//ios::sync_with_stdio(0);
//cin.tie(0);
//freopen("test_input.txt", "r", stdin);
//freopen("test_output.txt", "w", stdout);
    int n,q;ll s,t;
    cin>>n>>q>>s>>t;
    n++;
    a.resize(n);
    REP(i,0,n)cin>>a[i];
    b.resize(4*n+1,0);
    ll x=0,y=0;
    vi cu(n,0);
    REP(i,0,n-1)(a[i]<a[i+1]?x+=abs(a[i]-a[i+1]):y+=abs(a[i]-a[i+1]));
    REP(i,0,n-1)if(a[i]<a[i+1])cu[i]=1;
    while(q--){
        int c,d,e;cin>>c>>d>>e;
        ll g1=find(0,n-1,1,c-1);
        ll g2=find(0,n-1,1,c);
        if(cu[c-1])x-=abs(g1-g2);
        else y-=abs(g1-g2);
        if(d!=n-1){
            g1=find(0,n-1,1,d);
            g2=find(0,n-1,1,d+1);
            if(cu[d])x-=abs(g1-g2);
            else y-=abs(g1-g2);
        }
        update(0,n-1,1,c,d,(ll)e);
        ll val1=find(0,n-1,1,c-1);
        ll val2=find(0,n-1,1,c);
        //cout<<val1<<" "<<val2<<"\n";
        if(val1<val2){
            cu[c-1]=1;
            x+=abs(val1-val2);
        }
        else{
            cu[c-1]=0;
            y+=abs(val1-val2);
        }
        if(d!=n-1){
            val1=find(0,n-1,1,d);
            val2=find(0,n-1,1,d+1);//cout<<val1<<" "<<val2<<"\n";
            if(val1<val2){
                cu[d]=1;
                x+=abs(val1-val2);
            }
            else{
                cu[d]=0;
                y+=abs(val1-val2);
            }
        }
        //cout<<x<<" "<<y<<"\n";
        cout<<t*y-x*s<<"\n";
    }
}

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