Submission #1122199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122199		Hamed_Ghaffari	ZIGZAG (INOI20_zigzag)	C++17	100 / 100	716 ms	97692 KiB

Main

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

using ll = long long;

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 3e5+5;

struct Node {
    ll ans, L, R;
    int sz, LD, LU, RD, RU;
} seg[MXN<<2];
struct Lazy {
    ll sum;
    bool mul;
    Lazy() {sum=0, mul=0;}
    Lazy(ll a, bool b) {sum=a, mul=b;}
} lz[MXN<<2];

Node Merge(Node x, Node y) {
    Node res;
    res.L = x.L; res.R = y.R;
    res.sz = x.sz+y.sz;
    if(x.R<y.L) {
        res.ans = (x.ans + y.ans + (ll)x.RU*y.LD);
        res.LD = x.LD + (x.LD == x.sz && x.sz%2 == 0 ? y.LD : 0);
        res.LU = x.LU + (x.LU == x.sz && x.sz%2 ? y.LD : 0);
        res.RD = y.RD + (y.RD == y.sz && y.sz%2 ? x.RU : 0);
        res.RU = y.RU + (y.RU == y.sz && y.sz%2 == 0 ? x.RU : 0);
    }
    else if(x.R>y.L) {
        res.ans = (x.ans + y.ans + (ll)x.RD*y.LU);
        res.LD = x.LD + (x.LD == x.sz && x.sz%2 ? y.LU : 0);
        res.LU = x.LU + (x.LU == x.sz && x.sz%2 == 0 ? y.LU : 0);
        res.RD = y.RD + (y.RD == y.sz && y.sz%2 == 0 ? x.RD : 0);
        res.RU = y.RU + (y.RU == y.sz && y.sz%2 ? x.RD : 0);
    }
    else {
        res.ans = (x.ans+y.ans);
        res.LD = x.LD;
        res.LU = x.LU;
        res.RD = y.RD;
        res.RU = y.RU;
    }
    return res;
}

int n, a[MXN];

void Build(int l=1, int r=n+1, int id=1) {
    lz[id].sum = 0;
    lz[id].mul = 0;
    if(r-l == 1) {
        seg[id].ans = 1;
        seg[id].L = seg[id].R = a[l];
        seg[id].sz = 1;
        seg[id].LD = seg[id].LU = seg[id].RD = seg[id].RU = 1;
        return;
    }
    Build(l, mid, lc);
    Build(mid, r, rc);
    seg[id] = Merge(seg[lc], seg[rc]);
}
void Apply(Lazy dat, int id) {
    if(dat.mul) {
        swap(seg[id].LD, seg[id].LU);
        swap(seg[id].RD, seg[id].RU);
        seg[id].L *= -1;
        seg[id].R *= -1;
        lz[id].mul ^= 1;
        lz[id].sum *= -1;
    }
    seg[id].L += dat.sum;
    seg[id].R += dat.sum;
    lz[id].sum += dat.sum;
}
void Shift(int l, int r, int id) {
    if(r-l>1) {
        Apply(lz[id], lc);
        Apply(lz[id], rc);
    }
    lz[id].sum = 0;
    lz[id].mul = 0;
}
void Upd(int s, int e, Lazy x, int l=1, int r=n+1, int id=1) {
    Shift(l, r, id);
    if(s<=l && r<=e) {
        Apply(x, id);
        return;
    }
    if(s<mid) Upd(s,e,x, l, mid, lc);
    if(e>mid) Upd(s,e,x, mid, r, rc);
    seg[id] = Merge(seg[lc], seg[rc]);
}
Node Get(int s, int e, int l=1, int r=n+1, int id=1) {
    Shift(l, r, id);
    if(s<=l && r<=e) return seg[id];
    if(e<=mid) return Get(s, e, l, mid, lc);
    if(s>=mid) return Get(s, e, mid, r, rc);
    return Merge(Get(s, e, l, mid, lc), Get(s, e, mid, r, rc));
}

int q;

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    Build();
    while(q--) {
        char tp;
        int l, r;
        cin >> tp >> l >> r; r++;
        if(tp == '+') {
            int x;
            cin >> x;
            Upd(l, r, Lazy(x, 0));
        }
        else if(tp == '*') Upd(l, r, Lazy(0, 1));
        else if(tp == '?') cout << Get(l, r).ans << '\n';
    }
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 42 / 42
• Subtask 3: 35 / 35
• Subtask 4: 15 / 15