Submission #779223

# Submission time Handle Problem Language Result Execution time Memory
779223 2023-07-11T09:13:26 Z RushB ZIGZAG (INOI20_zigzag) C++17
0 / 100
281 ms 76496 KB
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 
#define int int64_t
const int64_t INF = 1ll << 60;
const int N = 3e5 + 5;
int n, q, a[N], b[N];

struct seg {
        int tool = 0, jam = 0, lz = 1, pref = 0, suf = 0, last = 0, fi = 0, ans = 0;
} S[N << 2], I;

inline int sgn(int x) {
        if (x == 0) return 0;
        return (x < 0 ? -1 : +1);
}
void print(int v, int l, int r) {
        if (l + 1 == r) {
                cout << S[v].jam << ' ';
                return;
        }
        int m = l + r >> 1;
        print(v << 1, l, m);
        print(v << 1 | 1, m, r);
}

void apply(int v) { //zarb * -1
        S[v].jam *= -1; 
        S[v].last *= -1;
        S[v].fi *= -1;
        S[v].lz *= -1;
}
inline void push(int v) {
        if (S[v].lz == -1) {
                apply(v << 1), apply(v << 1 | 1);
                S[v].lz = 1;
        }
}
void merge(seg &v, seg l, seg r) {
        v.jam = l.jam + r.jam;
        v.pref = (l.pref == l.tool && l.fi && r.fi && ((sgn(l.fi) == sgn(r.fi) && l.tool % 2 == 0) || (sgn(l.fi) != sgn(r.fi) && l.tool % 2 == 1)) ? l.pref + r.pref : l.pref);
        v.suf = (r.suf == r.tool && r.last && l.last && ((sgn(l.last) == sgn(r.last) && r.tool % 2 == 0) || (sgn(l.last) != sgn(r.last) && r.tool % 2 == 1)) ? r.suf + l.suf : r.suf);
        v.last = r.last;
        v.fi = l.fi;
        v.ans = l.ans + r.ans;
        v.ans += (l.last && r.fi && sgn(l.last) != sgn(r.fi) ? l.suf * r.pref : 0);
}
void upd(int v, int l, int r, int ind, int x) {
        if (l + 1 == r) {
                S[v].jam += x;
                S[v].fi = S[v].last = S[v].jam;
                S[v].pref = S[v].suf = S[v].ans = S[v].jam != 0;
                return;
        }
        push(v);
        int m = l + r >> 1;
        if (ind < m) upd(v << 1, l, m, ind, x);
        else upd(v << 1 | 1, m, r, ind, x);
        merge(S[v], S[v << 1], S[v << 1 | 1]);
}
void mult(int v, int l, int r, int L, int R) {
        if (R <= l || r <= L) return;
        if (L <= l && r <= R) {
                apply(v);
                return;
        }
        push(v);
        int m = l + r >> 1;
        mult(v << 1, l, m, L, R);
        mult(v << 1 | 1, m, r, L, R);
        merge(S[v], S[v << 1], S[v << 1 | 1]);
}
int get_sum(int v, int l, int r, int L, int R) {
        if (R <= l || r <= L) return 0;
        if (L <= l && r <= R) return S[v].jam;
        push(v);
        int m = l + r >> 1;
        int s = get_sum(v << 1, l, m, L, R) + get_sum(v << 1 | 1, m, r, L, R);
        merge(S[v], S[v << 1], S[v << 1 | 1]);
        return s;
}

seg get_ans(int v, int l, int r, int L, int R) {
        if (R <= l || r <= L) return I;
        if (L <= l && r <= R) return S[v];
        int m = l + r >> 1;
        push(v);
        seg x;
        merge(x, get_ans(v << 1, l, m, L, R), get_ans(v << 1 | 1, m, r, L, R));
        merge(S[v], S[v << 1], S[v << 1 | 1]);
        return x;
}

void build(int v, int l, int r) {
        S[v].tool = r - l;
        if (l + 1 == r) {
                S[v].fi = S[v].last = S[v].jam = b[l];
                S[v].lz = 1;
                S[v].pref = S[v].suf = S[v].ans = b[l] != 0;
                return;
        }
        int m = l + r >> 1;
        build(v << 1, l, m);
        build(v << 1 | 1, m, r);
        merge(S[v], S[v << 1], S[v << 1 | 1]);
}

signed main() {
        ios::sync_with_stdio(0), cin.tie(0);
        cin >> n >> q;
        FOR(i, 1, n + 1) cin >> a[i];
        FOR(i, 1, n + 1) b[i - 1] = a[i] - a[i - 1];
        build(1, 0, n);
        FOR(i, 0, q) {
                //print(1, 0, n);
                //cout << endl;
                string c; int l, r, x;
                cin >> c >> l >> r;
                if (c[0] == '?') {
                        int re = 0;
                        if (r > l) re += get_ans(1, 0, n, l, r).ans;
                        re += r - l + 1;
                        cout << re << '\n';
                }
                else if (c[0] == '\\') {
                       mult(1, 0, n, l, r); 
                       int lth = get_sum(1, 0, n, 0, l);
                       int rth = get_sum(1, 0, n, 0, r);
                       upd(1, 0, n, l - 1, -2 * lth);
                       if (r < n) upd(1, 0, n, r, 2 * rth);
                }
                else if (c[0] == '+') {
                       cin >> x; 
                       upd(1, 0, n, l - 1, +x);
                       if (r < n) upd(1, 0, n, r, -x);
                }
        }
        return 0;
}
//11:42:29

Compilation message

Main.cpp: In function 'void print(int64_t, int64_t, int64_t)':
Main.cpp:22:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In function 'void upd(int64_t, int64_t, int64_t, int64_t, int64_t)':
Main.cpp:56:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In function 'void mult(int64_t, int64_t, int64_t, int64_t, int64_t)':
Main.cpp:68:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In function 'int64_t get_sum(int64_t, int64_t, int64_t, int64_t, int64_t)':
Main.cpp:77:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In function 'seg get_ans(int64_t, int64_t, int64_t, int64_t, int64_t)':
Main.cpp:86:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In function 'void build(int64_t, int64_t, int64_t)':
Main.cpp:102:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |         int m = l + r >> 1;
      |                 ~~^~~
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 281 ms 76496 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -