/*
* 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
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];
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
17640 KB |
Output is correct |
2 |
Correct |
3 ms |
17640 KB |
Output is correct |
3 |
Correct |
3 ms |
17640 KB |
Output is correct |
4 |
Correct |
3 ms |
17640 KB |
Output is correct |
5 |
Correct |
3 ms |
17640 KB |
Output is correct |
6 |
Correct |
3 ms |
17640 KB |
Output is correct |
7 |
Correct |
3 ms |
17640 KB |
Output is correct |
8 |
Correct |
0 ms |
17640 KB |
Output is correct |
9 |
Correct |
3 ms |
17640 KB |
Output is correct |
10 |
Correct |
3 ms |
17640 KB |
Output is correct |
11 |
Correct |
3 ms |
17640 KB |
Output is correct |
12 |
Correct |
3 ms |
17640 KB |
Output is correct |
13 |
Correct |
0 ms |
17640 KB |
Output is correct |
14 |
Correct |
3 ms |
17640 KB |
Output is correct |
15 |
Correct |
3 ms |
17640 KB |
Output is correct |
16 |
Correct |
3 ms |
17640 KB |
Output is correct |
17 |
Correct |
0 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
873 ms |
17640 KB |
Output is correct |
2 |
Correct |
843 ms |
17640 KB |
Output is correct |
3 |
Correct |
819 ms |
17640 KB |
Output is correct |
4 |
Correct |
679 ms |
17640 KB |
Output is correct |
5 |
Correct |
923 ms |
17640 KB |
Output is correct |
6 |
Correct |
303 ms |
17640 KB |
Output is correct |
7 |
Correct |
306 ms |
17640 KB |
Output is correct |
8 |
Correct |
666 ms |
17640 KB |
Output is correct |
9 |
Correct |
739 ms |
17640 KB |
Output is correct |
10 |
Correct |
656 ms |
17640 KB |
Output is correct |
11 |
Correct |
336 ms |
17640 KB |
Output is correct |
12 |
Correct |
356 ms |
17640 KB |
Output is correct |
13 |
Correct |
319 ms |
17640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
17640 KB |
Output is correct |
2 |
Correct |
3 ms |
17640 KB |
Output is correct |
3 |
Correct |
3 ms |
17640 KB |
Output is correct |
4 |
Correct |
3 ms |
17640 KB |
Output is correct |
5 |
Correct |
3 ms |
17640 KB |
Output is correct |
6 |
Correct |
3 ms |
17640 KB |
Output is correct |
7 |
Correct |
3 ms |
17640 KB |
Output is correct |
8 |
Correct |
0 ms |
17640 KB |
Output is correct |
9 |
Correct |
3 ms |
17640 KB |
Output is correct |
10 |
Correct |
3 ms |
17640 KB |
Output is correct |
11 |
Correct |
3 ms |
17640 KB |
Output is correct |
12 |
Correct |
3 ms |
17640 KB |
Output is correct |
13 |
Correct |
0 ms |
17640 KB |
Output is correct |
14 |
Correct |
3 ms |
17640 KB |
Output is correct |
15 |
Correct |
3 ms |
17640 KB |
Output is correct |
16 |
Correct |
3 ms |
17640 KB |
Output is correct |
17 |
Correct |
0 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 |
Correct |
873 ms |
17640 KB |
Output is correct |
23 |
Correct |
843 ms |
17640 KB |
Output is correct |
24 |
Correct |
819 ms |
17640 KB |
Output is correct |
25 |
Correct |
679 ms |
17640 KB |
Output is correct |
26 |
Correct |
923 ms |
17640 KB |
Output is correct |
27 |
Correct |
303 ms |
17640 KB |
Output is correct |
28 |
Correct |
306 ms |
17640 KB |
Output is correct |
29 |
Correct |
666 ms |
17640 KB |
Output is correct |
30 |
Correct |
739 ms |
17640 KB |
Output is correct |
31 |
Correct |
656 ms |
17640 KB |
Output is correct |
32 |
Correct |
336 ms |
17640 KB |
Output is correct |
33 |
Correct |
356 ms |
17640 KB |
Output is correct |
34 |
Correct |
319 ms |
17640 KB |
Output is correct |
35 |
Correct |
906 ms |
17640 KB |
Output is correct |
36 |
Correct |
756 ms |
17640 KB |
Output is correct |
37 |
Correct |
813 ms |
17640 KB |
Output is correct |
38 |
Correct |
813 ms |
17640 KB |
Output is correct |
39 |
Correct |
799 ms |
17640 KB |
Output is correct |
40 |
Correct |
886 ms |
17640 KB |
Output is correct |
41 |
Correct |
836 ms |
17640 KB |
Output is correct |
42 |
Correct |
763 ms |
17640 KB |
Output is correct |
43 |
Correct |
879 ms |
17640 KB |
Output is correct |
44 |
Correct |
806 ms |
17640 KB |
Output is correct |
45 |
Correct |
696 ms |
17640 KB |
Output is correct |
46 |
Correct |
846 ms |
17640 KB |
Output is correct |
47 |
Correct |
306 ms |
17640 KB |
Output is correct |
48 |
Correct |
396 ms |
17640 KB |
Output is correct |
49 |
Correct |
763 ms |
17640 KB |
Output is correct |
50 |
Correct |
393 ms |
17640 KB |
Output is correct |
51 |
Correct |
313 ms |
17640 KB |
Output is correct |
52 |
Correct |
413 ms |
17640 KB |
Output is correct |