oj.uz

Submission #779276

# Submission time Handle Problem Language Result Execution time Memory
779276 2023-07-11T09:44:32 Z RushB ZIGZAG (INOI20_zigzag) C++17
100 / 100
 1010 ms 79944 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 
#define int long long
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 (L == l && r == R) return S[v];
        int m = l + r >> 1;
        push(v);
        if (R <= m) return get_ans(v << 1, l, m, L, R);
        else if (L >= m) return get_ans(v << 1 | 1, m, r, L, R);
        seg x;
        merge(x, get_ans(v << 1, l, m, L, m), get_ans(v << 1 | 1, m, r, m, R));
        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] == '*') {
                       int lth = get_sum(1, 0, n, 0, l);
                       int rth = get_sum(1, 0, n, 0, r);
                       mult(1, 0, n, l, 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);
                }
        }
        cout << endl;
        return 0;
}
//11:42:29

Compilation message

Main.cpp: In function 'void print(long long int, long long int, long long int)':
Main.cpp:22:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:56:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In function 'void mult(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:68:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In function 'long long int get_sum(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:77:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In function 'seg get_ans(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:85:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         int m = l + r >> 1;
      |                 ~~^~~
Main.cpp: In function 'void build(long long int, long long int, long long int)':
Main.cpp:102:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |         int m = l + r >> 1;
      |                 ~~^~~

Subtask #1
8.0 / 8.0

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

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 71608 KB Output is correct
2 Correct 237 ms 2516 KB Output is correct
3 Correct 895 ms 79588 KB Output is correct
4 Correct 931 ms 79564 KB Output is correct
5 Correct 885 ms 79524 KB Output is correct
6 Correct 867 ms 79568 KB Output is correct
7 Correct 856 ms 76452 KB Output is correct
8 Correct 957 ms 79576 KB Output is correct
9 Correct 897 ms 79484 KB Output is correct
10 Correct 774 ms 79616 KB Output is correct
11 Correct 874 ms 79524 KB Output is correct
12 Correct 892 ms 79500 KB Output is correct
13 Correct 849 ms 79512 KB Output is correct
14 Correct 816 ms 79464 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1492 KB Output is correct
2 Correct 12 ms 1492 KB Output is correct
3 Correct 16 ms 1492 KB Output is correct
4 Correct 12 ms 1492 KB Output is correct
5 Correct 14 ms 1492 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 12 ms 1492 KB Output is correct
8 Correct 273 ms 20112 KB Output is correct
9 Correct 277 ms 20168 KB Output is correct
10 Correct 296 ms 21180 KB Output is correct
11 Correct 231 ms 20756 KB Output is correct
12 Correct 298 ms 21196 KB Output is correct
13 Correct 291 ms 21196 KB Output is correct
14 Correct 274 ms 21120 KB Output is correct
15 Correct 263 ms 20084 KB Output is correct
16 Correct 302 ms 21140 KB Output is correct
17 Correct 294 ms 21276 KB Output is correct
18 Correct 269 ms 21068 KB Output is correct
19 Correct 273 ms 21080 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1492 KB Output is correct
2 Correct 12 ms 1492 KB Output is correct
3 Correct 16 ms 1492 KB Output is correct
4 Correct 12 ms 1492 KB Output is correct
5 Correct 14 ms 1492 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 12 ms 1492 KB Output is correct
8 Correct 834 ms 71608 KB Output is correct
9 Correct 237 ms 2516 KB Output is correct
10 Correct 895 ms 79588 KB Output is correct
11 Correct 931 ms 79564 KB Output is correct
12 Correct 885 ms 79524 KB Output is correct
13 Correct 867 ms 79568 KB Output is correct
14 Correct 856 ms 76452 KB Output is correct
15 Correct 957 ms 79576 KB Output is correct
16 Correct 897 ms 79484 KB Output is correct
17 Correct 774 ms 79616 KB Output is correct
18 Correct 874 ms 79524 KB Output is correct
19 Correct 892 ms 79500 KB Output is correct
20 Correct 849 ms 79512 KB Output is correct
21 Correct 816 ms 79464 KB Output is correct
22 Correct 273 ms 20112 KB Output is correct
23 Correct 277 ms 20168 KB Output is correct
24 Correct 296 ms 21180 KB Output is correct
25 Correct 231 ms 20756 KB Output is correct
26 Correct 298 ms 21196 KB Output is correct
27 Correct 291 ms 21196 KB Output is correct
28 Correct 274 ms 21120 KB Output is correct
29 Correct 263 ms 20084 KB Output is correct
30 Correct 302 ms 21140 KB Output is correct
31 Correct 294 ms 21276 KB Output is correct
32 Correct 269 ms 21068 KB Output is correct
33 Correct 273 ms 21080 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 240 KB Output is correct
36 Correct 917 ms 76712 KB Output is correct
37 Correct 974 ms 79816 KB Output is correct
38 Correct 712 ms 78712 KB Output is correct
39 Correct 972 ms 79712 KB Output is correct
40 Correct 933 ms 76776 KB Output is correct
41 Correct 891 ms 79724 KB Output is correct
42 Correct 857 ms 76880 KB Output is correct
43 Correct 953 ms 79748 KB Output is correct
44 Correct 1010 ms 79744 KB Output is correct
45 Correct 945 ms 79728 KB Output is correct
46 Correct 904 ms 79808 KB Output is correct
47 Correct 910 ms 79944 KB Output is correct