Submission #29393

#	Time	Username	Problem	Language	Result	Execution time	Memory
29393		PrOAhMeT	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	30 / 100	416 ms	5924 KiB

foehn_phenomena

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN=200015;
int n,q,a[MAXN];
LL s,tt;

struct fenwick_tree {
	
	LL fen[MAXN];

	void upd(int x,LL y) {

		++x;
		for(;x<MAXN;x+=x&(-x))
			fen[x]+=y;

	}

	LL get(int x) {

		++x;
		LL ret=0;
		for(;x;x-=x&(-x))
			ret+=fen[x];
		return ret;

	}

} h,t;

int main() {

	cin>>n>>q>>s>>tt;
	LL temp=0;
	for(int i=0;i<=n;++i) {
		cin>>a[i];
		if(i>0) {
			if(a[i]>a[i-1]) {
				t.upd(i,-s*(a[i]-a[i-1]));
			}
			else {
				t.upd(i,tt*(a[i-1]-a[i]));
			}
		}
		if(i) h.upd(i,a[i]-a[i-1]);
		else h.upd(i,a[i]);
	}
	int l,r,x;
	LL bef,cur,beft,curt,nw;
	for(int i=0;i<q;++i) {
		cin>>l>>r>>x;
		LL oldl,oldr;
		if(l>0)
			oldl=t.get(l)-t.get(l-1);
		if(r<n)
			oldr=t.get(r+1)-t.get(r);
		h.upd(l,x);
		h.upd(r+1,-x);
		if(l>0) {
			bef=h.get(l-1);
			cur=h.get(l);
			if(bef>cur) {
				t.upd(l,tt*(bef-cur)-oldl);
			}
			else t.upd(l,-s*(cur-bef)-oldl);
		}
		if(r<n) {
			bef=h.get(r);
			cur=h.get(r+1);
			if(cur<bef) {
				t.upd(r+1,tt*(bef-cur)-oldr);
			}
			else t.upd(r+1,-s*(cur-bef)-oldr);
		}
		//cout<<"update "<<i+1<<endl;
		//for(int j=0;j<=n;++j)
			//cout<<j<<" "<<t.get(j)<<" "<<h.get(j)<<endl;
		printf("%lld\n",t.get(n));
	}

}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:42:5: warning: unused variable 'temp' [-Wunused-variable]
  LL temp=0;
     ^
foehn_phenomena.cpp:57:13: warning: unused variable 'beft' [-Wunused-variable]
  LL bef,cur,beft,curt,nw;
             ^
foehn_phenomena.cpp:57:18: warning: unused variable 'curt' [-Wunused-variable]
  LL bef,cur,beft,curt,nw;
                  ^
foehn_phenomena.cpp:57:23: warning: unused variable 'nw' [-Wunused-variable]
  LL bef,cur,beft,curt,nw;
                       ^
foehn_phenomena.cpp:73:14: warning: 'oldl' may be used uninitialized in this function [-Wmaybe-uninitialized]
    else t.upd(l,-s*(cur-bef)-oldl);
              ^

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