Submission #76753

#	Time	Username	Problem	Language	Result	Execution time	Memory
76753		Vardanyan	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	30 / 100	1079 ms	19508 KiB

foehn_phenomena

//#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
const int N = 200*1000+7;
int a[N];
long long t[2][4*N];
long long T[4*N];
long long f[4*N];
inline void push(int v,int s,int e){
    if(f[v]){
        T[v] += ((e-s+1)*f[v]);
        if(s!=e){
            f[v*2] += f[v];
            f[v*2+1] += f[v];
        }
    }
    f[v] = 0;
}
inline void update(int v,int s,int e,int l,int r,int val){
    push(v,s,e);
    if(l>r) return;
    if(s == l && e == r){
        f[v] += val;
        return;
    }
    int m = (s+e)/2;
    update(v*2,s,m,l,min(m,r),val);
    update(v*2+1,m+1,e,max(l,m+1),r,val);
    push(v*2,s,m);
    push(v*2+1,m+1,e);
    T[v] = T[v*2]+T[v*2+1];
}
inline long long query(int v,int s,int e,int l,int r){
    push(v,s,e);
    if(l>r) return 0;
    if(s == l && e == r) return T[v];
    int m = (s+e)/2;
    return query(v*2,s,m,l,min(m,r))+query(v*2+1,m+1,e,max(l,m+1),r);
}
inline void update2(int nshan,int v,int s,int e,int l,int r,int val){
    if(l>r) return;
    if(s == l && e == r){
        t[nshan][v] = val;
        return;
    }
    int m = (s+e)/2;
    update2(nshan,v*2,s,m,l,min(m,r),val);
    update2(nshan,v*2+1,m+1,e,max(l,m+1),r,val);
    t[nshan][v] = t[nshan][v*2]+t[nshan][v*2+1];
}
inline long long query2(int nshan,int v,int s,int e,int l,int r){
    if(l>r) return 0;
    if(s == l && e == r) return t[nshan][v];
    int m = (s+e)/2;
    return query2(nshan,v*2,s,m,l,min(m,r))+
           query2(nshan,v*2+1,m+1,e,max(l,m+1),r);
}
int main(){
    int n,q;
    int ss,tt;
    scanf("%d%d%d%d",&n,&q,&ss,&tt);
    for(int i = 0;i<=n;i++){
            scanf("%d",&a[i]);
            update(1,0,n,i,i,a[i]);
    }
    for(int i = 1;i<=n;i++){
        long long df = a[i-1]-a[i];
        if(df>=0){
            update2(1,1,1,n,i,i,df);
        }
        else{
            update2(0,1,1,n,i,i,df);
        }
    }
    /*
    for(int i = 1;i<=n;i++){
        cout<<query2(1,1,1,n,i,i)<<endl;
    }*/
    while(q--){
        int l,r;
        int val;
        scanf("%d%d%d",&l,&r,&val);
        update2(0,1,1,n,l,l,0);
        update2(1,1,1,n,l,l,0);
        update(1,0,n,l,r,val);
        long long x = query(1,0,n,l,l);
        long long y = query(1,0,n,l-1,l-1);
        y-=x;
        if(y<0) {
            update2(0,1,1,n,l,l,y);
        }
        else{
            update2(1,1,1,n,l,l,y);
        }
        if(r<n){
        update2(0,1,1,n,r+1,r+1,0);
        update2(1,1,1,n,r+1,r+1,0);
        x = query(1,0,n,r,r);
        y = query(1,0,n,r+1,r+1);
        x-=y;
        if(x<0){
            update2(0,1,1,n,r+1,r+1,x);
        }
        else{
            update2(1,1,1,n,r+1,r+1,x);
        }
        }
        long long w = query2(0,1,1,n,1,n);
   //     cout<<w<<endl;
        w*=ss;
        long long e = query2(1,1,1,n,1,n);
   //     cout<<e<<endl;
        e*=tt;
        w+=e;
        printf("%lld\n",w);
        /*for(int i = 1;i<=n;i++){
            cout<<query2(0,1,1,n,i,i)<<" "<<query2(1,1,1,n,i,i)<<endl;
        }*/
    }

    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d",&n,&q,&ss,&tt);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:63:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a[i]);
             ~~~~~^~~~~~~~~~~~
foehn_phenomena.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&l,&r,&val);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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