Submission #907493

# Submission time Handle Problem Language Result Execution time Memory
907493 2024-01-15T17:46:34 Z a_l_i_r_e_z_a Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
1 ms 348 KB
// In the name of God

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((ll)(x).size())

const int maxn = 2e5 + 5;
const ll inf = 1e16 + 7;
int n, q, a[maxn];
ll lazy[maxn << 2];
struct D{
    ll ans, left, right, al, ar, is;
} node[maxn << 2];

D combine(D x, D y){
    D res = {x.ans + y.ans, x.left, y.right, x.al, y.ar, 1};
    if(x.right == y.left) return res;
    if(x.right > y.left){
        ll delta = x.right - y.left;
        if(x.ar != -inf) delta -= abs(x.ar - x.right);
        if(y.al != -inf) delta -= abs(y.al - y.left);
        if(delta <= 0) return res;
        res.ans += delta;
        if(!x.is){
            if(x.al == -inf) res.al == y.left;
            else if(x.al == x.right){
                if(x.left < x.right) res.al = -inf;
            }
        } 
        if(!y.is){
            if(y.ar == -inf) res.ar = x.right;
            else if(y.ar == y.left){
                if(y.right > y.left) res.ar = -inf;
            }
        }
        if(x.is == 0 && y.is == 0){
            if(x.ar == -inf || x.ar > x.right){
                if(y.al == -inf || y.al < x.left) res.is = 0;
            }
        }
    }
    if(x.right < y.left){
        ll delta = abs(x.right - y.left);
        if(x.ar != -inf) delta -= abs(x.ar - x.right);
        if(y.al != -inf) delta -= abs(y.al - y.left);
        if(delta <= 0) return res;
        res.ans += delta;
        if(!x.is){
            if(x.al == -inf) res.al == y.left;
            else if(x.al == x.right){
                if(x.left > x.right) res.al = -inf;
            }
        } 
        if(!y.is){
            if(y.ar == -inf) res.ar = x.right;
            else if(y.ar == y.left){
                if(y.right < y.left) res.ar = -inf;
            }
        }
        if(x.is == 0 && y.is == 0){
            if(x.ar == -inf || x.ar < x.right){
                if(y.al == -inf || y.al > x.left) res.is = 0;
            }
        }
    }
    return res;
}

void build(int l = 0, int r = n, int id = 1){
    if(l == r - 1){
        node[id].ans = 0;
        node[id].left = a[l];
        node[id].right = a[l];
        node[id].al = -inf;
        node[id].ar = -inf;
        node[id].is = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, id * 2);
    build(mid, r, id * 2 + 1);
    node[id] = combine(node[id * 2], node[id * 2 + 1]);
}

void change(ll x, int id){
    node[id].right += x;
    node[id].left += x;
    if(node[id].al != -inf) node[id].al += x;
    if(node[id].ar != -inf) node[id].ar += x;
    lazy[id] += x;
}

void relax(int id){
    change(lazy[id], id * 2);
    change(lazy[id], id * 2 + 1);
    lazy[id] = 0;
}

void upd(int s, int e, ll x, int l = 0, int r = n, int id = 1){
    if(s <= l && r <= e){
        change(x, id);
        return;
    }
    if(e <= l || r <= s) return;
    relax(id);
    int mid = (l + r) / 2;
    upd(s, e, x, l, mid, id * 2);
    upd(s, e, x, mid, r, id * 2 + 1);
    node[id] = combine(node[id * 2], node[id * 2 + 1]);
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> a[i];
    build();
    while(q--){
        ll l, r, x; cin >> l >> r >> x;
        l--;
        upd(l, r, x);
        cout << node[1].ans << '\n';
    }

    return 0;
}

Compilation message

Main.cpp: In function 'D combine(D, D)':
Main.cpp:38:37: warning: statement has no effect [-Wunused-value]
   38 |             if(x.al == -inf) res.al == y.left;
      |                              ~~~~~~~^~~~~~~~~
Main.cpp:62:37: warning: statement has no effect [-Wunused-value]
   62 |             if(x.al == -inf) res.al == y.left;
      |                              ~~~~~~~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -