oj.uz

Submission #673779

# Submission time Handle Problem Language Result Execution time Memory
673779 2022-12-22T02:43:48 Z Trent Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 1071 ms 46948 KB 
#include "bits/stdc++.h"
#include <cstring>
#include <fstream>

using namespace std;

#define ll long long
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define open(s) freopen(((string) s + ".in").c_str(), "r", stdin); freopen(((string) s + ".out").c_str(), "w", stdout)
#define all(i) i.begin(), i.end()
#define boost() cin.sync_with_stdio(0); cin.tie()
#define int ll

int sign(int g){
    return g == 0 ? 0 : g > 0 ? 1 : -1;
}

const int MN = 2e5 + 10, ME=4*MN;
// maximum total value if we remove [left][right]; lazy increase; left & right value; left & right sign (nex - cur)
struct node{int tot[2][2], lInc, lef, rig, lSig, rSig;};
node seg[ME];

void push(int v){
    if(2 * v + 1 < ME){
        seg[2*v].lef += seg[v].lInc;
        seg[2*v].rig += seg[v].lInc;
        seg[2*v+1].lef += seg[v].lInc;
        seg[2*v+1].rig += seg[v].lInc;
        seg[2*v].lInc += seg[v].lInc;
        seg[2*v+1].lInc += seg[v].lInc;
        seg[v].lInc = 0;
    }
}

void upd(int v, int nl, int nr, int ul, int ur, int by){
    if(nl > ur || nr < ul) return;
    else if(nl == ul && nr == ur){
        seg[v].lInc += by;
        seg[v].lef += by;
        seg[v].rig += by;
    } else {
        push(v);
        int mid = (nl + nr) / 2;
        upd(2*v, nl, mid, ul, min(mid, ur), by);
        upd(2*v+1, mid+1, nr, max(mid+1, ul), ur, by);

        seg[v].lef = seg[2*v].lef;
        seg[v].rig = seg[2*v+1].rig;
        assert(seg[v].lInc == 0);
        forR(lr, 2) forR(rr, 2){
            int& edit = seg[v].tot[lr][rr];
            edit = seg[2*v].tot[lr][0] + seg[2*v+1].tot[0][rr];

            if(nr - mid - rr > 0 && mid - nl + 1 - lr > 0){
                int delta = seg[2*v+1].lef - seg[2*v].rig;
                int dSign = sign(delta);
                int lefAdd = seg[2*v].rSig == dSign ? seg[2*v].tot[lr][0] : seg[2*v].tot[lr][1];
                int rigAdd = seg[2*v+1].lSig == dSign ? seg[2*v+1].tot[0][rr] : seg[2*v+1].tot[1][rr];
                edit = max(edit, lefAdd + abs(delta) + rigAdd);
            }
        }
        seg[v].lSig = mid > nl ? seg[2*v].lSig : sign(seg[2*v+1].lef - seg[2*v].rig);
        seg[v].rSig = mid + 1 < nr ? seg[2*v+1].rSig : sign(seg[2*v+1].lef - seg[2*v].rig);
    }
}


signed main() {
    int n, q; cin >> n >> q;
    REP(i, 1, n + 1) {
        int v; cin >> v;
        upd(1, 1, n, i, i, v);
    }
    forR(g, q){
        int l, r, x; cin >> l >> r >> x;
        upd(1, 1, n, l, r, x);
        cout << seg[1].tot[0][0] << '\n';
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 13 ms 940 KB Output is correct
8 Correct 12 ms 980 KB Output is correct
9 Correct 12 ms 916 KB Output is correct
10 Correct 12 ms 988 KB Output is correct
11 Correct 12 ms 924 KB Output is correct
12 Correct 11 ms 944 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 13 ms 940 KB Output is correct
8 Correct 12 ms 980 KB Output is correct
9 Correct 12 ms 916 KB Output is correct
10 Correct 12 ms 988 KB Output is correct
11 Correct 12 ms 924 KB Output is correct
12 Correct 11 ms 944 KB Output is correct
13 Correct 1044 ms 46280 KB Output is correct
14 Correct 1071 ms 46296 KB Output is correct
15 Correct 1022 ms 46412 KB Output is correct
16 Correct 1051 ms 46232 KB Output is correct
17 Correct 1063 ms 46148 KB Output is correct
18 Correct 997 ms 46948 KB Output is correct