Submission #398450

#	Time	Username	Problem	Language	Result	Execution time	Memory
398450		lukameladze	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	519 ms	16284 KiB

foehn_phenomena

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=3e5+5;
long long n,m,s,t,a[N],pr[N],le,ri,ad,prl,l,r,nxr,tree[2*N],tree2[2*N],xx,xx1;
void update1(long long idx, long long  val) {
     for (long long  i=idx; i<=N; i+=i&(-i)) {
          tree[i]+=val;
     }
}
long long getans1(long long  idx) {
     long long pas=0;
     for (long long  i=idx; i>0; i-=i&(-i)) {
          pas+=tree[i];
     }
     return pas;
}
void update2(long long  idx, long long  val) {
     for (long long  i=idx; i<=N; i+=i&(-i)) {
          tree2[i]+=val;
     }
}
long long getans2(long long  idx) {
     long long pas=0;
     for (long long  i=idx; i>0; i-=i&(-i)) {
          pas+=tree2[i];
     }
     return pas;
}
long long go(long long  a, long long  b) {
     if (a<b) return -abs(a-b)*s;
     else return abs(a-b)*t;
}
int main() {
     std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
     cin>>n>>m>>s>>t;
     for (int i=1; i<=n+1; i++) {
          cin>>a[i];
          update1(i,a[i]);
          update1(i+1, -a[i]);
     }
     //cout<<getans1(1)<<endl<<endl;
     pr[1]=0;
     for (int i=2; i<=n+1; i++) {
    		long long ww=go(a[i-1],a[i]);
    	//	cout<<i<<"    "<<ww<<endl;
          pr[i]=pr[i-1]+ww;
          update2(i,ww);
         // update2(i+1, -ww);
     }
    // cout<<getans2(n+1)<<endl<<endl<<endl;
     for (int i=1; i<=m; i++) {
          cin>>le>>ri>>ad;
          le++;
          ri++;
          l=getans1(le);
          prl=getans1(le-1);
          xx=go(prl,l);
          xx1=go(prl,l+ad);          
		  //cout<<prl<<" "<<l<<" "<<xx<<" "<<xx1<<endl;
          update2(le,xx1-xx);
          //cout<<getans2(n+1)<<endl<<endl;
          //update2(r+1, xx-xx1);
          r=getans1(ri);
          nxr=getans1(ri+1);
          
          xx=go(r,nxr);
          xx1=go(r+ad,nxr);//cout<<r<<" "<<nxr<<" "<<xx<<" "<<xx1<<endl;
          update2(ri+1, xx1-xx);
          cout<<getans2(n+1)<<endl;
          update1(le,ad);
          update1(ri+1, -ad);
     }
}

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