oj.uz

Submission #39542

# Submission time Handle Problem Language Result Execution time Memory
39542 2018-01-16T10:28:13 Z comtalyst Foehn Phenomena (JOI17_foehn_phenomena) C++14
30 / 100
 1000 ms 17640 KB 
/*
 *	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;
	
	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++;
		res += (sm_get(1,1,n,x,x)-sm_get(1,1,n,x-1,x-1))*sv[sm_get(1,1,n,x,x)-sm_get(1,1,n,x-1,x-1) > 0];
		if(y < n) res += (sm_get(1,1,n,y+1,y+1)-sm_get(1,1,n,y,y))*sv[sm_get(1,1,n,y+1,y+1)-sm_get(1,1,n,y,y) > 0];
		sm_up(1,1,n,x,y,v);
		res -= (sm_get(1,1,n,x,x)-sm_get(1,1,n,x-1,x-1))*sv[sm_get(1,1,n,x,x)-sm_get(1,1,n,x-1,x-1) > 0];
		if(y < n) res -= (sm_get(1,1,n,y+1,y+1)-sm_get(1,1,n,y,y))*sv[sm_get(1,1,n,y+1,y+1)-sm_get(1,1,n,y,y) > 0];
		printf("%lld\n",res);
	}

	return 0;	
}

Compilation message

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;
           ^
foehn_phenomena.cpp:74:15: warning: unused variable 'm' [-Wunused-variable]
  long t,i,j,n,m,v,res=0,x,y,lv=0;
               ^
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);
                                   ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17640 KB Output is correct
2 Correct 6 ms 17640 KB Output is correct
3 Correct 9 ms 17640 KB Output is correct
4 Correct 6 ms 17640 KB Output is correct
5 Correct 9 ms 17640 KB Output is correct
6 Correct 6 ms 17640 KB Output is correct
7 Correct 6 ms 17640 KB Output is correct
8 Correct 9 ms 17640 KB Output is correct
9 Correct 6 ms 17640 KB Output is correct
10 Correct 6 ms 17640 KB Output is correct
11 Correct 6 ms 17640 KB Output is correct
12 Correct 6 ms 17640 KB Output is correct
13 Correct 3 ms 17640 KB Output is correct
14 Correct 3 ms 17640 KB Output is correct
15 Correct 6 ms 17640 KB Output is correct
16 Correct 3 ms 17640 KB Output is correct
17 Correct 3 ms 17640 KB Output is correct
18 Correct 3 ms 17640 KB Output is correct
19 Correct 0 ms 17640 KB Output is correct
20 Correct 0 ms 17640 KB Output is correct
21 Correct 0 ms 17640 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 17640 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 17640 KB Output is correct
2 Correct 6 ms 17640 KB Output is correct
3 Correct 9 ms 17640 KB Output is correct
4 Correct 6 ms 17640 KB Output is correct
5 Correct 9 ms 17640 KB Output is correct
6 Correct 6 ms 17640 KB Output is correct
7 Correct 6 ms 17640 KB Output is correct
8 Correct 9 ms 17640 KB Output is correct
9 Correct 6 ms 17640 KB Output is correct
10 Correct 6 ms 17640 KB Output is correct
11 Correct 6 ms 17640 KB Output is correct
12 Correct 6 ms 17640 KB Output is correct
13 Correct 3 ms 17640 KB Output is correct
14 Correct 3 ms 17640 KB Output is correct
15 Correct 6 ms 17640 KB Output is correct
16 Correct 3 ms 17640 KB Output is correct
17 Correct 3 ms 17640 KB Output is correct
18 Correct 3 ms 17640 KB Output is correct
19 Correct 0 ms 17640 KB Output is correct
20 Correct 0 ms 17640 KB Output is correct
21 Correct 0 ms 17640 KB Output is correct
22 Execution timed out 1000 ms 17640 KB Execution timed out
23 Halted 0 ms 0 KB -