oj.uz

Submission #931535

# Submission time Handle Problem Language Result Execution time Memory
931535 2024-02-22T02:51:46 Z AnasAAF Foehn Phenomena (JOI17_foehn_phenomena) C++17
30 / 100
 384 ms 28736 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define float double
#define ld long double

ll N = 2e5+10;
ll n, S, T, Q;
vector<ll>v(N);
vector<ll>tree(6*N);
vector<ll>lazy(6*N);

void update(int node, ll l, ll r, ll ql, ll qr, ll val){
    //cout<<node<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<val<<endl;
    if(lazy[node]!=0){
        tree[node]+=lazy[node]*(r-l+1);
        if(l!=r){
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
    }
    if(ql>r || qr<l)return;
    if(ql<=l && qr>=r){
        tree[node]+=(val*(r-l+1));
        //cout<<"BINGO"<<endl;
        if(l!=r){
            lazy[node*2]+=val;
            lazy[node*2+1]+=val;
        }
        return;
    }
    ll mid = (l+r)/2;
    update(node*2, l, mid, ql, qr, val);
    update(node*2+1, mid+1, r, ql, qr, val);
    return;
}

int get(int node, ll l, ll r, ll ind){
    if(lazy[node]!=0){
        tree[node]+=lazy[node]*(r-l+1);
        if(l!=r){
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
    }
    if(l==r)return tree[node];
    int mid = (l+r)/2;
    if(ind<=mid)return get(node*2, l, mid, ind);
    else return get(node*2+1, mid+1, r, ind);
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>Q>>S>>T;
    for(int i=0;i<=n;i++)cin>>v[i];
    ll nxp2 = (1<<(ll)ceil(log2(double(N))));
    for(int i=0;i<=n;i++){
        update(1, 0, nxp2, i, i, v[i]);
    }
    ll ans(0);
    for(int i=0;i<n;i++){
        if(v[i]<v[i+1])ans-=(v[i+1]-v[i])*S;
        else ans+=(v[i]-v[i+1])*T;
    }
    while(Q--){
        ll l, r, x;cin>>l>>r>>x;
        ll bl = get(1, 0, nxp2, l-1);
        ll al = get(1, 0, nxp2, l);
        ll br, ar;
        br = get(1, 0, nxp2, r);
        if(r!=n)ar = get(1, 0, nxp2, r+1);

        if(bl<al)ans+=(al-bl)*S;
        else ans-=(bl-al)*T;
        if(r!=n){
            if(br<ar)ans+=(ar-br)*S;
            else ans-=(br-ar)*T;
        }

        update(1, 0, nxp2, l, r, x);
        //for(int i=0;i<=n;i++)cout<<get(1, 0, nxp2, i)<<" ";
        //cout<<endl;

        bl = get(1, 0, nxp2, l-1);
        al = get(1, 0, nxp2, l);
        br = get(1, 0, nxp2, r);
        if(r!=n)ar = get(1, 0, nxp2, r+1);
        if(bl<al)ans-=(al-bl)*S;
        else ans+=(bl-al)*T;
        if(r!=n){
            if(br<ar)ans-=(ar-br)*S;
            else ans+=(br-ar)*T;
        }
        cout<<ans<<endl;
    }

    return 0;
}

Compilation message

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:80:26: warning: 'ar' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |             else ans-=(br-ar)*T;
      |                       ~~~^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20824 KB Output is correct
2 Correct 7 ms 20828 KB Output is correct
3 Correct 8 ms 20656 KB Output is correct
4 Correct 7 ms 20904 KB Output is correct
5 Correct 7 ms 20832 KB Output is correct
6 Correct 7 ms 20828 KB Output is correct
7 Correct 7 ms 20828 KB Output is correct
8 Correct 7 ms 20828 KB Output is correct
9 Correct 7 ms 20840 KB Output is correct
10 Correct 8 ms 20836 KB Output is correct
11 Correct 7 ms 20828 KB Output is correct
12 Correct 7 ms 20828 KB Output is correct
13 Correct 6 ms 20828 KB Output is correct
14 Correct 6 ms 20828 KB Output is correct
15 Correct 7 ms 20828 KB Output is correct
16 Correct 6 ms 20828 KB Output is correct
17 Correct 6 ms 20828 KB Output is correct
18 Correct 6 ms 20824 KB Output is correct
19 Correct 4 ms 20572 KB Output is correct
20 Correct 5 ms 20572 KB Output is correct
21 Correct 4 ms 20572 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 25884 KB Output is correct
2 Correct 358 ms 28244 KB Output is correct
3 Correct 375 ms 28736 KB Output is correct
4 Incorrect 360 ms 28636 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 20824 KB Output is correct
2 Correct 7 ms 20828 KB Output is correct
3 Correct 8 ms 20656 KB Output is correct
4 Correct 7 ms 20904 KB Output is correct
5 Correct 7 ms 20832 KB Output is correct
6 Correct 7 ms 20828 KB Output is correct
7 Correct 7 ms 20828 KB Output is correct
8 Correct 7 ms 20828 KB Output is correct
9 Correct 7 ms 20840 KB Output is correct
10 Correct 8 ms 20836 KB Output is correct
11 Correct 7 ms 20828 KB Output is correct
12 Correct 7 ms 20828 KB Output is correct
13 Correct 6 ms 20828 KB Output is correct
14 Correct 6 ms 20828 KB Output is correct
15 Correct 7 ms 20828 KB Output is correct
16 Correct 6 ms 20828 KB Output is correct
17 Correct 6 ms 20828 KB Output is correct
18 Correct 6 ms 20824 KB Output is correct
19 Correct 4 ms 20572 KB Output is correct
20 Correct 5 ms 20572 KB Output is correct
21 Correct 4 ms 20572 KB Output is correct
22 Correct 384 ms 25884 KB Output is correct
23 Correct 358 ms 28244 KB Output is correct
24 Correct 375 ms 28736 KB Output is correct
25 Incorrect 360 ms 28636 KB Output isn't correct
26 Halted 0 ms 0 KB -