# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
204165 | 2020-02-24T19:06:15 Z | mdn2002 | Foehn Phenomena (JOI17_foehn_phenomena) | C++14 | 954 ms | 13432 KB |
#include<bits/stdc++.h> using namespace std; const long long mod=998244353; long long n,q,s,t,ps[200005],a[200005],ans,sqt; vector<pair<int,pair<int,int> > >v; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //freopen(".in","r",stdin); //freopen(".out","w",stdout); scanf("%lld",&n); scanf("%lld",&q); scanf("%lld",&s); scanf("%lld",&t); sqt=ceil(sqrt(q)); long long b; scanf("%lld",&b); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); long long aa=a[i]; long long dif=b-aa; if(dif>=0)ans+=dif*t; else ans+=dif*s; b=aa; } long long l,r,x,dif=0; while(q--) { scanf("%lld",&l); scanf("%lld",&r); scanf("%lld",&x); long long la=a[l],ra=a[r],oa=a[l-1],va=a[r+1]; for(int i=0;i<v.size();i++) { long long ll=v[i].first,rr=v[i].second.first,xx=v[i].second.second; if(ll<=l&&l<=rr)la+=xx; if(ll<=r&&r<=rr)ra+=xx; if(ll<=l-1&&l-1<=rr)oa+=xx; if(ll<=r+1&&r+1<=rr)va+=xx; } v.push_back({l,{r,x}}); long long ll=la+x,rr=ra+x; if(l>0) { dif=oa-la; if(dif>=0)ans-=dif*t; else ans-=dif*s; dif=oa-ll; if(dif>=0)ans+=dif*t; else ans+=dif*s; } if(r<n) { dif=ra-va; if(dif>=0)ans-=dif*t; else ans-=dif*s; dif=rr-va; if(dif>=0)ans+=dif*t; else ans+=dif*s; } printf("%lld\n",ans); if(v.size()<sqt)continue; for(int i=0;i<v.size();i++) { long long ll=v[i].first,rr=v[i].second.first,xx=v[i].second.second; ps[ll]+=xx,ps[rr+1]-=xx; } for(int i=1;i<=n;i++) { ps[i]+=ps[i-1]; a[i]+=ps[i]; } for(int i=1;i<=n;i++)ps[i]=0; v.clear(); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 376 KB | Output is correct |
2 | Correct | 7 ms | 376 KB | Output is correct |
3 | Correct | 7 ms | 376 KB | Output is correct |
4 | Correct | 7 ms | 376 KB | Output is correct |
5 | Correct | 7 ms | 376 KB | Output is correct |
6 | Correct | 7 ms | 376 KB | Output is correct |
7 | Correct | 8 ms | 376 KB | Output is correct |
8 | Correct | 7 ms | 376 KB | Output is correct |
9 | Correct | 7 ms | 376 KB | Output is correct |
10 | Correct | 7 ms | 376 KB | Output is correct |
11 | Correct | 8 ms | 380 KB | Output is correct |
12 | Correct | 7 ms | 376 KB | Output is correct |
13 | Correct | 6 ms | 376 KB | Output is correct |
14 | Correct | 7 ms | 504 KB | Output is correct |
15 | Correct | 7 ms | 376 KB | Output is correct |
16 | Correct | 7 ms | 376 KB | Output is correct |
17 | Correct | 7 ms | 376 KB | Output is correct |
18 | Correct | 7 ms | 376 KB | Output is correct |
19 | Correct | 5 ms | 376 KB | Output is correct |
20 | Correct | 5 ms | 376 KB | Output is correct |
21 | Correct | 5 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 935 ms | 5012 KB | Output is correct |
2 | Correct | 946 ms | 11128 KB | Output is correct |
3 | Correct | 946 ms | 11512 KB | Output is correct |
4 | Correct | 934 ms | 11256 KB | Output is correct |
5 | Correct | 937 ms | 12152 KB | Output is correct |
6 | Correct | 693 ms | 11256 KB | Output is correct |
7 | Correct | 692 ms | 11128 KB | Output is correct |
8 | Correct | 902 ms | 12024 KB | Output is correct |
9 | Correct | 904 ms | 12440 KB | Output is correct |
10 | Correct | 897 ms | 11000 KB | Output is correct |
11 | Correct | 685 ms | 11000 KB | Output is correct |
12 | Correct | 688 ms | 11896 KB | Output is correct |
13 | Correct | 678 ms | 11896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 376 KB | Output is correct |
2 | Correct | 7 ms | 376 KB | Output is correct |
3 | Correct | 7 ms | 376 KB | Output is correct |
4 | Correct | 7 ms | 376 KB | Output is correct |
5 | Correct | 7 ms | 376 KB | Output is correct |
6 | Correct | 7 ms | 376 KB | Output is correct |
7 | Correct | 8 ms | 376 KB | Output is correct |
8 | Correct | 7 ms | 376 KB | Output is correct |
9 | Correct | 7 ms | 376 KB | Output is correct |
10 | Correct | 7 ms | 376 KB | Output is correct |
11 | Correct | 8 ms | 380 KB | Output is correct |
12 | Correct | 7 ms | 376 KB | Output is correct |
13 | Correct | 6 ms | 376 KB | Output is correct |
14 | Correct | 7 ms | 504 KB | Output is correct |
15 | Correct | 7 ms | 376 KB | Output is correct |
16 | Correct | 7 ms | 376 KB | Output is correct |
17 | Correct | 7 ms | 376 KB | Output is correct |
18 | Correct | 7 ms | 376 KB | Output is correct |
19 | Correct | 5 ms | 376 KB | Output is correct |
20 | Correct | 5 ms | 376 KB | Output is correct |
21 | Correct | 5 ms | 376 KB | Output is correct |
22 | Correct | 935 ms | 5012 KB | Output is correct |
23 | Correct | 946 ms | 11128 KB | Output is correct |
24 | Correct | 946 ms | 11512 KB | Output is correct |
25 | Correct | 934 ms | 11256 KB | Output is correct |
26 | Correct | 937 ms | 12152 KB | Output is correct |
27 | Correct | 693 ms | 11256 KB | Output is correct |
28 | Correct | 692 ms | 11128 KB | Output is correct |
29 | Correct | 902 ms | 12024 KB | Output is correct |
30 | Correct | 904 ms | 12440 KB | Output is correct |
31 | Correct | 897 ms | 11000 KB | Output is correct |
32 | Correct | 685 ms | 11000 KB | Output is correct |
33 | Correct | 688 ms | 11896 KB | Output is correct |
34 | Correct | 678 ms | 11896 KB | Output is correct |
35 | Correct | 948 ms | 10540 KB | Output is correct |
36 | Correct | 931 ms | 12024 KB | Output is correct |
37 | Correct | 943 ms | 12920 KB | Output is correct |
38 | Correct | 945 ms | 12664 KB | Output is correct |
39 | Correct | 946 ms | 12536 KB | Output is correct |
40 | Correct | 954 ms | 12536 KB | Output is correct |
41 | Correct | 951 ms | 12536 KB | Output is correct |
42 | Correct | 934 ms | 12500 KB | Output is correct |
43 | Correct | 946 ms | 11768 KB | Output is correct |
44 | Correct | 939 ms | 12488 KB | Output is correct |
45 | Correct | 925 ms | 12408 KB | Output is correct |
46 | Correct | 937 ms | 13432 KB | Output is correct |
47 | Correct | 706 ms | 11896 KB | Output is correct |
48 | Correct | 702 ms | 11804 KB | Output is correct |
49 | Correct | 935 ms | 10872 KB | Output is correct |
50 | Correct | 692 ms | 11644 KB | Output is correct |
51 | Correct | 689 ms | 12024 KB | Output is correct |
52 | Correct | 693 ms | 11768 KB | Output is correct |