oj.uz

Submission #522338

# Submission time Handle Problem Language Result Execution time Memory
522338 2022-02-04T16:02:00 Z perchuts Foehn Phenomena (JOI17_foehn_phenomena) C++17
100 / 100
 731 ms 19720 KB 
#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

ll v[2*maxn],seg[8*maxn],lazy[8*maxn];
int n,q;
ll s,t,sum;

void push(int i,int l,int r){
    if(l!=r)lazy[2*i]+=lazy[i],lazy[2*i+1]+=lazy[i];
    seg[i]+=lazy[i]*(1LL*(r-l+1));
    lazy[i] = 0;
}

void update(int i,int l,int r,int x,int y,ll d){
    push(i,l,r);
    if(l>y||r<x)return;
    if(x<=l&&r<=y){
        lazy[i]+=d;
        push(i,l,r);
        return;
    }
    int md = (l+r)/2;
    update(2*i,l,md,x,y,d);
    update(2*i+1,md+1,r,x,y,d);
    seg[i] = seg[2*i]+seg[2*i+1];
}

ll query(int i,int l,int r,int x){
    push(i,l,r);
    if(l>x||r<x)return 0;
    if(l==r)return seg[i];
    int md = (l+r)/2;
    return query(2*i,l,md,x) + query(2*i+1,md+1,r,x);
}

void updatesum(int i){
    ll l = query(1,1,n,i-1), r = query(1,1,n,i);
    sum-=v[i];
    if(l<=r)v[i] = (l-r)*(s);
    else v[i] = (l-r)*(t);
    sum+=v[i];   

}

int main(){_
    cin>>n>>q>>s>>t;
    ll last = 0;
    n++;
    for(int i=1;i<=n;i++){
        ll x;cin>>x;
        update(1,1,n,i,i,x);
        if(i!=1)updatesum(i);
        last = x;
        // cout<<sum<<" ";
    }
    // cout<<endl; 0 18 7
    while(q--){
        int l,r;
        ll x;cin>>l>>r>>x;l++,r++;
        update(1,1,n,l,r,x);
        if(r!=n)updatesum(r+1);
        updatesum(l);
        cout<<sum<<endl;
    }
}

Compilation message

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:63:8: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   63 |     ll last = 0;
      |        ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 444 KB Output is correct
2 Correct 4 ms 444 KB Output is correct
3 Correct 5 ms 460 KB Output is correct
4 Correct 4 ms 456 KB Output is correct
5 Correct 5 ms 408 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 5 ms 460 KB Output is correct
8 Correct 7 ms 464 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 5 ms 444 KB Output is correct
11 Correct 7 ms 460 KB Output is correct
12 Correct 4 ms 464 KB Output is correct
13 Correct 4 ms 460 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Correct 7 ms 460 KB Output is correct
16 Correct 4 ms 476 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 7 ms 460 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 320 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 16984 KB Output is correct
2 Correct 661 ms 17448 KB Output is correct
3 Correct 587 ms 18160 KB Output is correct
4 Correct 585 ms 17524 KB Output is correct
5 Correct 589 ms 18756 KB Output is correct
6 Correct 338 ms 17796 KB Output is correct
7 Correct 333 ms 17608 KB Output is correct
8 Correct 489 ms 18452 KB Output is correct
9 Correct 496 ms 18752 KB Output is correct
10 Correct 495 ms 17476 KB Output is correct
11 Correct 413 ms 17488 KB Output is correct
12 Correct 340 ms 18228 KB Output is correct
13 Correct 338 ms 18552 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 444 KB Output is correct
2 Correct 4 ms 444 KB Output is correct
3 Correct 5 ms 460 KB Output is correct
4 Correct 4 ms 456 KB Output is correct
5 Correct 5 ms 408 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 5 ms 460 KB Output is correct
8 Correct 7 ms 464 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 5 ms 444 KB Output is correct
11 Correct 7 ms 460 KB Output is correct
12 Correct 4 ms 464 KB Output is correct
13 Correct 4 ms 460 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Correct 7 ms 460 KB Output is correct
16 Correct 4 ms 476 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 7 ms 460 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 320 KB Output is correct
22 Correct 639 ms 16984 KB Output is correct
23 Correct 661 ms 17448 KB Output is correct
24 Correct 587 ms 18160 KB Output is correct
25 Correct 585 ms 17524 KB Output is correct
26 Correct 589 ms 18756 KB Output is correct
27 Correct 338 ms 17796 KB Output is correct
28 Correct 333 ms 17608 KB Output is correct
29 Correct 489 ms 18452 KB Output is correct
30 Correct 496 ms 18752 KB Output is correct
31 Correct 495 ms 17476 KB Output is correct
32 Correct 413 ms 17488 KB Output is correct
33 Correct 340 ms 18228 KB Output is correct
34 Correct 338 ms 18552 KB Output is correct
35 Correct 612 ms 17072 KB Output is correct
36 Correct 612 ms 18456 KB Output is correct
37 Correct 615 ms 19268 KB Output is correct
38 Correct 633 ms 19060 KB Output is correct
39 Correct 629 ms 19000 KB Output is correct
40 Correct 625 ms 19052 KB Output is correct
41 Correct 671 ms 18884 KB Output is correct
42 Correct 670 ms 19036 KB Output is correct
43 Correct 689 ms 18332 KB Output is correct
44 Correct 731 ms 18744 KB Output is correct
45 Correct 620 ms 18664 KB Output is correct
46 Correct 620 ms 19720 KB Output is correct
47 Correct 389 ms 18360 KB Output is correct
48 Correct 405 ms 18300 KB Output is correct
49 Correct 601 ms 17284 KB Output is correct
50 Correct 430 ms 18048 KB Output is correct
51 Correct 385 ms 18464 KB Output is correct
52 Correct 489 ms 18324 KB Output is correct