Submission #631922

#	Time	Username	Problem	Language	Result	Execution time	Memory
631922		AA_Surely	ZIGZAG (INOI20_zigzag)	C++14	100 / 100	1193 ms	98832 KiB

Main

#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 (rs < ls) return;
        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 (rs < ls) return;
        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 (rs < ls) return;
        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 (rs < ls || 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: 8 / 8
• Subtask 2: 42 / 42
• Subtask 3: 35 / 35
• Subtask 4: 15 / 15