oj.uz

Submission #631919

# Submission time Handle Problem Language Result Execution time Memory
631919 2022-08-19T07:11:41 Z AA_Surely ZIGZAG (INOI20_zigzag) C++17
42 / 100
 917 ms 98492 KB 
#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define U(x) (x < 0 ? -1 : (x == 0 ? 0 : 1))

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

#define lc now << 1
#define rc now << 1 | 1
#define endl '\n'

const int N = 3e5 + 2;

LL n, q;
LL ns[N];

struct NumTree {
    PLL lz[N << 2];
    
    void build() {
        F0R(i, (N << 2)) lz[i].F = 1;
        return;
    }

    void addLz(int now, PLL v) {
        lz[now].F *= v.F;
        lz[now].S *= v.F;
        lz[now].S += v.S;
        return;
    }

    void shift(int now) {
        addLz(lc, lz[now]);
        addLz(rc, lz[now]);

        lz[now].F = 1; lz[now].S = 0;
    }

    void upd(int lq, int rq, PLL val, int now = 1, int ls = 0, int rs = n - 1) {
        if (rq < lq || rq < ls || rs < lq) return;
        if (lq <= ls && rs <= rq) return addLz(now, val);
        int mid = (ls + rs) >> 1;
        shift(now);
        upd(lq, rq, val, lc, ls, mid); upd(lq, rq, val, rc, mid + 1, rs);
        return;
    }

    LL get(int id, int now = 1, int ls = 0, int rs = n - 1) {
        if (ls == rs) return ns[ls] * lz[now].F + lz[now].S;
        int mid = (ls + rs) >> 1;
        shift(now);
        if (id <= mid) return get(id, lc, ls, mid);
        return get(id, rc, mid + 1, rs);
    }
} num;

struct Node {
    LL lft, rgt;
    LL pref, suff, len;
    LL ans;
};

inline Node operator + (const Node &a, const Node &b) {
    if (!a.len) return b;
    if (!b.len) return a;

    Node c;

    c.lft = a.lft; 
    c.rgt = b.rgt;
    c.len = a.len + b.len;
    c.pref = a.pref + (a.pref == a.len && (!!U(a.rgt) && !!U(b.lft)) && U(a.rgt) != U(b.lft) ? b.pref : 0LL);
    c.suff = b.suff + (b.suff == b.len && (!!U(a.rgt) && !!U(b.lft)) && U(a.rgt) != U(b.lft)? a.suff : 0LL);
    c.ans = a.ans + b.ans + ((!!U(a.rgt) && !!U(b.lft)) && U(a.rgt) != U(b.lft) ? a.suff * b.pref : 0LL);

    return c;
}

struct ZigZagTree {
    Node tree[N << 2];
    PLL lz[N << 2];

    void addLz(int now, PLL v) {
        tree[now].lft *= v.F;
        tree[now].lft += v.S;

        tree[now].rgt *= v.F;
        tree[now].rgt += v.S;
        
        lz[now].F *= v.F;
        lz[now].S *= v.F;
        lz[now].S += v.S;
        return;
    }

    inline void shift(int now) {
        addLz(lc, lz[now]);
        addLz(rc, lz[now]);

        lz[now] = {1, 0};
        return;
    }

    void build(int now = 1, int ls = 0, int rs = n - 2) {
        if (ls == rs) {
            lz[now].F = 1;
            tree[now].lft = tree[now].rgt = ns[ls + 1] - ns[ls];
            tree[now].len = 1;
            tree[now].suff = tree[now].pref = tree[now].ans = (!!U(ns[ls + 1] - ns[ls]));
            return;
        }
    
        int mid = (ls + rs) >> 1;
        lz[now].F = 1;
        build(lc, ls, mid); build(rc, mid + 1, rs);
        tree[now] = tree[lc] + tree[rc];

        return;
    }

    void change(int id, LL val, int now = 1, int ls = 0, int rs = n - 2) {
        if (ls == rs) {
            tree[now].lft = tree[now].rgt = val;
            tree[now].pref = tree[now].suff = tree[now].ans = !!val;
            return;
        }

        int mid = (ls + rs) >> 1;
        shift(now);

        if (id <= mid) change(id, val, lc, ls, mid);
        else change(id, val, rc, mid + 1, rs);

        tree[now] = tree[lc] + tree[rc];
        return;
    }

    void mult(int lq, int rq, int now = 1, int ls = 0, int rs = n - 2) {
        if (rq < lq || rq < ls || rs < lq) return;
        if (lq <= ls && rs <= rq) return addLz(now, {-1, 0});

        int mid = (ls + rs) >> 1;
        shift(now);

        mult(lq, rq, lc, ls, mid); mult(lq, rq, rc, mid + 1, rs);
        tree[now] = tree[lc] + tree[rc];
        return;
    }

    Node get(int lq, int rq, int now = 1, int ls = 0, int rs = n - 2) {
        if (rq < lq || rq < ls || rs < lq) return tree[0];
        if (lq <= ls && rs <= rq) return tree[now];
        int mid = (ls + rs) >> 1;
        shift(now);
        return get(lq, rq, lc, ls, mid) + get(lq, rq, rc, mid + 1, rs);
    }

} zig;

void init() {
    cin >> n >> q;
    F0R(i, n) cin >> ns[i];

    num.build();
    zig.build();

    return;
}

void cross() {
    int l, r; 
    cin >> l >> r;
    l--; r--;

    num.upd(l, r, {-1, 0});
    zig.mult(l, r - 1);
    
    if (l) {
        LL p1 = num.get(l - 1);
        LL p2 = num.get(l);
        zig.change(l - 1, p2 - p1);
    }

    if (r != n - 1) {
        LL p1 = num.get(r);
        LL p2 = num.get(r + 1);
        zig.change(r, p2 - p1);
    }

    return;
}

void pls() {
    int l, r, v;
    cin >> l >> r >> v;
    l--; r--;

    num.upd(l, r, {1, v});

    if (l) {
        LL p1 = num.get(l - 1);
        LL p2 = num.get(l);
        zig.change(l - 1, p2 - p1);
    }

    if (r != n - 1) {
        LL p1 = num.get(r);
        LL p2 = num.get(r + 1);
        zig.change(r, p2 - p1);
    }
}


void query() {
    int l, r;
    cin >> l >> r;
    l--; r--;
    
    cout << zig.get(l, r - 1).ans + (r - l + 1) << endl;
    return;
}

int main() {
    IOS;
    
    init();
    
    while(q--) {
        char tp; cin >> tp;
        if (tp == '*') cross();
        if (tp == '+') pls();
        if (tp == '?') query();
    }

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 38740 KB Output is correct
2 Correct 23 ms 38728 KB Output is correct
3 Correct 26 ms 38612 KB Output is correct
4 Correct 26 ms 38656 KB Output is correct
5 Correct 25 ms 38612 KB Output is correct
6 Runtime error 50 ms 76584 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 863 ms 90184 KB Output is correct
2 Correct 71 ms 40108 KB Output is correct
3 Correct 778 ms 98324 KB Output is correct
4 Correct 894 ms 98460 KB Output is correct
5 Correct 825 ms 98412 KB Output is correct
6 Correct 806 ms 98492 KB Output is correct
7 Correct 917 ms 95300 KB Output is correct
8 Correct 869 ms 98324 KB Output is correct
9 Correct 839 ms 98420 KB Output is correct
10 Correct 631 ms 98352 KB Output is correct
11 Correct 804 ms 98420 KB Output is correct
12 Correct 894 ms 98452 KB Output is correct
13 Correct 480 ms 98392 KB Output is correct
14 Correct 479 ms 98268 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 38740 KB Output is correct
2 Correct 23 ms 38728 KB Output is correct
3 Correct 26 ms 38612 KB Output is correct
4 Correct 26 ms 38656 KB Output is correct
5 Correct 25 ms 38612 KB Output is correct
6 Runtime error 50 ms 76584 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 38740 KB Output is correct
2 Correct 23 ms 38728 KB Output is correct
3 Correct 26 ms 38612 KB Output is correct
4 Correct 26 ms 38656 KB Output is correct
5 Correct 25 ms 38612 KB Output is correct
6 Runtime error 50 ms 76584 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -