# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
954155 | 2024-03-27T10:47:50 Z | StefanSebez | Foehn Phenomena (JOI17_foehn_phenomena) | C++14 | 137 ms | 16892 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long const int N=3*1e5+500; ll p[N+50]; void Update(int i,ll qval){ for(;i<=N;i+=i&(-i)) p[i]+=qval; } ll Get(int i){ ll sum=0; for(;i>=1;i-=i&(-i)) sum+=p[i]; return sum; } //int Sum(int l,int r){return Get(r)-Get(l-1);} int main() { int n,q;ll S,T;scanf("%i%i%lld%lld",&n,&q,&S,&T); ll a[N+50];for(int i=0;i<=n;i++) scanf("%lld",&a[i]); ll b[N+50],res=0; for(int i=1;i<=n;i++){ if(a[i-1]<a[i]) b[i]=(a[i-1]-a[i])*S; else b[i]=(a[i-1]-a[i])*T; res+=b[i]; } //printf("%i\n",res); while(q--){ int l,r;ll x;scanf("%i%i%lld",&l,&r,&x); Update(l,x);Update(r+1,-x); ll temp=b[l],u=Get(l-1)+a[l-1],v=Get(l)+a[l]; if(u<v) b[l]=(u-v)*S; else b[l]=(u-v)*T; res+=b[l]-temp; //printf("%i %i %i %i\n",u,v,temp,b[l]); if(r+1<=n){ temp=b[r+1],u=Get(r)+a[r],v=Get(r+1)+a[r+1]; if(u<v) b[r+1]=(u-v)*S; else b[r+1]=(u-v)*T; res+=b[r+1]-temp; } printf("%lld\n",res); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7000 KB | Output is correct |
2 | Correct | 4 ms | 7004 KB | Output is correct |
3 | Correct | 4 ms | 7260 KB | Output is correct |
4 | Correct | 4 ms | 7004 KB | Output is correct |
5 | Correct | 4 ms | 7004 KB | Output is correct |
6 | Correct | 4 ms | 7004 KB | Output is correct |
7 | Correct | 4 ms | 7188 KB | Output is correct |
8 | Correct | 4 ms | 7256 KB | Output is correct |
9 | Correct | 4 ms | 7004 KB | Output is correct |
10 | Correct | 3 ms | 7004 KB | Output is correct |
11 | Correct | 5 ms | 7004 KB | Output is correct |
12 | Correct | 4 ms | 7260 KB | Output is correct |
13 | Correct | 4 ms | 7004 KB | Output is correct |
14 | Correct | 4 ms | 7216 KB | Output is correct |
15 | Correct | 4 ms | 7120 KB | Output is correct |
16 | Correct | 4 ms | 7004 KB | Output is correct |
17 | Correct | 3 ms | 7004 KB | Output is correct |
18 | Correct | 4 ms | 7032 KB | Output is correct |
19 | Correct | 3 ms | 7004 KB | Output is correct |
20 | Correct | 3 ms | 7004 KB | Output is correct |
21 | Correct | 3 ms | 7004 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 119 ms | 8704 KB | Output is correct |
2 | Correct | 102 ms | 9172 KB | Output is correct |
3 | Correct | 116 ms | 10128 KB | Output is correct |
4 | Correct | 105 ms | 9096 KB | Output is correct |
5 | Correct | 105 ms | 15820 KB | Output is correct |
6 | Correct | 93 ms | 14672 KB | Output is correct |
7 | Correct | 95 ms | 14680 KB | Output is correct |
8 | Correct | 106 ms | 15776 KB | Output is correct |
9 | Correct | 110 ms | 16160 KB | Output is correct |
10 | Correct | 109 ms | 14676 KB | Output is correct |
11 | Correct | 86 ms | 14676 KB | Output is correct |
12 | Correct | 84 ms | 15408 KB | Output is correct |
13 | Correct | 87 ms | 15440 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7000 KB | Output is correct |
2 | Correct | 4 ms | 7004 KB | Output is correct |
3 | Correct | 4 ms | 7260 KB | Output is correct |
4 | Correct | 4 ms | 7004 KB | Output is correct |
5 | Correct | 4 ms | 7004 KB | Output is correct |
6 | Correct | 4 ms | 7004 KB | Output is correct |
7 | Correct | 4 ms | 7188 KB | Output is correct |
8 | Correct | 4 ms | 7256 KB | Output is correct |
9 | Correct | 4 ms | 7004 KB | Output is correct |
10 | Correct | 3 ms | 7004 KB | Output is correct |
11 | Correct | 5 ms | 7004 KB | Output is correct |
12 | Correct | 4 ms | 7260 KB | Output is correct |
13 | Correct | 4 ms | 7004 KB | Output is correct |
14 | Correct | 4 ms | 7216 KB | Output is correct |
15 | Correct | 4 ms | 7120 KB | Output is correct |
16 | Correct | 4 ms | 7004 KB | Output is correct |
17 | Correct | 3 ms | 7004 KB | Output is correct |
18 | Correct | 4 ms | 7032 KB | Output is correct |
19 | Correct | 3 ms | 7004 KB | Output is correct |
20 | Correct | 3 ms | 7004 KB | Output is correct |
21 | Correct | 3 ms | 7004 KB | Output is correct |
22 | Correct | 119 ms | 8704 KB | Output is correct |
23 | Correct | 102 ms | 9172 KB | Output is correct |
24 | Correct | 116 ms | 10128 KB | Output is correct |
25 | Correct | 105 ms | 9096 KB | Output is correct |
26 | Correct | 105 ms | 15820 KB | Output is correct |
27 | Correct | 93 ms | 14672 KB | Output is correct |
28 | Correct | 95 ms | 14680 KB | Output is correct |
29 | Correct | 106 ms | 15776 KB | Output is correct |
30 | Correct | 110 ms | 16160 KB | Output is correct |
31 | Correct | 109 ms | 14676 KB | Output is correct |
32 | Correct | 86 ms | 14676 KB | Output is correct |
33 | Correct | 84 ms | 15408 KB | Output is correct |
34 | Correct | 87 ms | 15440 KB | Output is correct |
35 | Correct | 110 ms | 14164 KB | Output is correct |
36 | Correct | 114 ms | 15608 KB | Output is correct |
37 | Correct | 115 ms | 16432 KB | Output is correct |
38 | Correct | 115 ms | 16244 KB | Output is correct |
39 | Correct | 110 ms | 16148 KB | Output is correct |
40 | Correct | 107 ms | 16304 KB | Output is correct |
41 | Correct | 111 ms | 16036 KB | Output is correct |
42 | Correct | 121 ms | 16196 KB | Output is correct |
43 | Correct | 115 ms | 15440 KB | Output is correct |
44 | Correct | 107 ms | 15880 KB | Output is correct |
45 | Correct | 124 ms | 15852 KB | Output is correct |
46 | Correct | 113 ms | 16892 KB | Output is correct |
47 | Correct | 103 ms | 15384 KB | Output is correct |
48 | Correct | 101 ms | 15448 KB | Output is correct |
49 | Correct | 107 ms | 14644 KB | Output is correct |
50 | Correct | 137 ms | 15228 KB | Output is correct |
51 | Correct | 99 ms | 15612 KB | Output is correct |
52 | Correct | 89 ms | 15196 KB | Output is correct |