Submission #39543

#	Time	Username	Problem	Language	Result	Execution time	Memory
39543		comtalyst	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	923 ms	17640 KiB

foehn_phenomena

/*
 *	Task: JOI17_FOEHN_PHENOMENA
 *	Lang: C/C++11
 *	Author: comtalyst
 *	Site: oj.uz
 *	Last Update: 16/1/2018
 */

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
using namespace std;

/* Note
----------------------------
Learned : 
Bugs found & solved :
Optimizations :
----------------------------
*/	

#define x first
#define y second
#define umap unordered_map
#define pqueue priority_queue
#define mset multiset
#define mp make_pair
#define mt make_tuple
#define long long long
#define MOD 1000000007
#define MAX (long)2e9
#define MIN (long)-2e9
#define FILEIN_ freopen("__in.txt","r",stdin)
#define FILEOUT_ freopen("__out.txt","w",stdout)
#define FILEIN(text) freopen(text,"r",stdin)
#define FILEOUT(text) freopen(text,"w",stdout)

long sv[5],sm[1000005],sml[1000005];
void sm_up(long tidx,long l,long r,long x,long y,long w){
	long mid = (l+r)/2;
	if(x > r || y < l){
		return;
	}
	if(x <= l && y >= r){
		sml[tidx] += w;
		sm[tidx] += w*(r-l+1);
		return;
	}
	if(sml[tidx]){
		sm_up(tidx*2,l,mid,l,r,sml[tidx]);
		sm_up(tidx*2+1,mid+1,r,l,r,sml[tidx]);
		sml[tidx] = 0;
	}
	sm_up(tidx*2,l,mid,x,y,w);
	sm_up(tidx*2+1,mid+1,r,x,y,w);
	sm[tidx] = sm[tidx*2] + sm[tidx*2+1];
}
long sm_get(long tidx,long l,long r,long x,long y){
	long mid = (l+r)/2;
	if(x > r || y < l){
		return 0;
	}
	if(x <= l && y >= r){
		return sm[tidx];
	}
	if(sml[tidx]){
		sm_up(tidx*2,l,mid,l,r,sml[tidx]);
		sm_up(tidx*2+1,mid+1,r,l,r,sml[tidx]);
		sml[tidx] = 0;
	}
	return sm_get(tidx*2,l,mid,x,y) + sm_get(tidx*2+1,mid+1,r,x,y);
}

main(){
	long t,i,j,n,m,v,res=0,x,y,lv=0,xx,yy,xx2,yy2;
	
	scanf("%lld %lld %lld %lld",&n,&t,&sv[1],&sv[0]);
	n++;
	for(i = 1; i <= n; i++){
		scanf("%lld",&v);
		sm_up(1,1,n,i,i,v);
		res -= (v-lv)*sv[v-lv > 0];
		lv = v;
	}
//	printf("> %lld\n",res);
	while(t--){
		scanf("%lld %lld %lld",&x,&y,&v);
		x++;
		y++;
		xx = sm_get(1,1,n,x,x);
		yy = sm_get(1,1,n,x-1,x-1);
		res += (xx-yy)*sv[xx-yy > 0];
		if(y < n){
			xx2 = sm_get(1,1,n,y+1,y+1);
			yy2 = sm_get(1,1,n,y,y);
			res += (xx2-yy2)*sv[xx2-yy2 > 0];
		}
		sm_up(1,1,n,x,y,v);
		xx += v;
		res -= (xx-yy)*sv[xx-yy > 0];
		if(y < n){
			yy2 += v;
			res -= (xx2-yy2)*sv[xx2-yy2 > 0];
		}
		printf("%lld\n",res);
	}

	return 0;	
}

Compilation message (stderr)

foehn_phenomena.cpp:73:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:74:11: warning: unused variable 'j' [-Wunused-variable]
  long t,i,j,n,m,v,res=0,x,y,lv=0,xx,yy,xx2,yy2;
           ^
foehn_phenomena.cpp:74:15: warning: unused variable 'm' [-Wunused-variable]
  long t,i,j,n,m,v,res=0,x,y,lv=0,xx,yy,xx2,yy2;
               ^
foehn_phenomena.cpp:76:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld %lld",&n,&t,&sv[1],&sv[0]);
                                                  ^
foehn_phenomena.cpp:79:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&v);
                   ^
foehn_phenomena.cpp:86:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&x,&y,&v);
                                   ^
foehn_phenomena.cpp:101:12: warning: 'yy2' may be used uninitialized in this function [-Wmaybe-uninitialized]
    yy2 += v;
            ^
foehn_phenomena.cpp:102:27: warning: 'xx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
    res -= (xx2-yy2)*sv[xx2-yy2 > 0];
                           ^

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