oj.uz

Submission #681623

# Submission time Handle Problem Language Result Execution time Memory
681623 2023-01-13T13:16:20 Z stevancv Progression (NOI20_progression) C++14
35 / 100
 1312 ms 122980 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 3e5 + 2;
const ll linf = 9e18;
struct Segtree {
    ll st[4 * N], lzys[4 * N], lzya[4 * N];
    void Reset1(int n) {
        for (int i = 1; i <= 4 * n; i++) {
            lzys[i] = linf;
            st[i] = lzya[i] = 0;
        }
    }
    void Propagate1(int node, int l, int r) {
        if (lzys[node] == linf && lzya[node] == 0) return;
        if (l < r) {
            if (lzys[node] != linf) {
                lzys[2 * node] = lzys[2 * node + 1] = lzys[node];
                lzya[2 * node] = lzya[2 * node + 1] = 0;
            }
            if (lzya[node] != 0) {
                if (lzys[2 * node] != linf) lzys[2 * node] += lzya[node];
                else lzya[2 * node] += lzya[node];
                if (lzys[2 * node + 1] != linf) lzys[2 * node + 1] += lzya[node];
                else lzya[2 * node + 1] += lzya[node];
            }
        }
        if (lzys[node] != linf) {st[node] = lzys[node]; lzys[node] = linf;}
        if (lzya[node] != 0) {st[node] += lzya[node]; lzya[node] = 0;}
    }
    void Set1(int node, int l, int r, int ql, int qr, ll y) {
        Propagate1(node, l, r);
        if (r < ql || qr < l || ql > qr) return;
        if (ql <= l && r <= qr) {
            lzys[node] = y;
            Propagate1(node, l, r);
            return;
        }
        int mid = l + r >> 1;
        Set1(2 * node, l, mid, ql, qr, y);
        Set1(2 * node + 1, mid + 1, r, ql, qr, y);
        st[node] = min(st[2 * node], st[2 * node + 1]);
    }
    void Add1(int node, int l, int r, int ql, int qr, ll y) {
        Propagate1(node, l, r);
        if (r < ql || qr < l || ql > qr) return;
        if (ql <= l && r <= qr) {
            lzya[node] = y;
            Propagate1(node, l, r);
            return;
        }
        int mid = l + r >> 1;
        Add1(2 * node, l, mid, ql, qr, y);
        Add1(2 * node + 1, mid + 1, r, ql, qr, y);
        st[node] = min(st[2 * node], st[2 * node + 1]);
    }
    ll Get1(int node, int l, int r, int x) {
        Propagate1(node, l, r);
        if (l == r) return st[node];
        int mid = l + r >> 1;
        if (x <= mid) return Get1(2 * node, l, mid, x);
        return Get1(2 * node + 1, mid + 1, r, x);
    }
}st1, st2;
struct Node {
    int ans, llen, rlen, seg;
    ll lval, rval;
    Node() {
        ans = llen = rlen = seg = 0;
        lval = rval = linf;
    }
    Node(int a, int b, int c, int d, ll e, ll f) {
        ans = a; llen = b; rlen = c; seg = d; lval = e; rval = f;
    }
}st[4 * N];
Node Merge(Node a, Node b) {
    Node c = Node();
    if (a.lval == linf) {c = b; return c;}
    if (b.lval == linf) {c = a; return c;}
    c.ans = max(a.ans, b.ans); c.lval = a.lval; c.rval = b.rval; c.llen = a.llen; c.rlen = b.rlen; c.seg = a.seg + b.seg;
    if (a.rval != b.lval) return c;
    smax(c.ans, a.rlen + b.llen);
    if (a.llen == a.seg) c.llen += b.llen;
    if (b.rlen == b.seg) c.rlen += a.rlen;
    return c;
}
ll a[N], d[N], lzys[4 * N], lzya[4 * N];
void Init(int node, int l, int r) {
    lzys[node] = linf; lzya[node] = 0;
    if (l == r) {
        st[node] = Node(1, 1, 1, 1, d[l], d[l]);
        return;
    }
    int mid = l + r >> 1;
    Init(2 * node, l, mid);
    Init(2 * node + 1, mid + 1, r);
    st[node] = Merge(st[2 * node], st[2 * node + 1]);
}
void Propagate(int node, int l, int r) {
    if (lzys[node] == linf && lzya[node] == 0) return;
    if (l < r) {
        if (lzys[node] != linf) {
            lzys[2 * node] = lzys[2 * node + 1] = lzys[node];
            lzya[2 * node] = lzya[2 * node + 1] = 0;
        }
        if (lzya[node] != 0) {
            if (lzys[2 * node] != linf) lzys[2 * node] += lzya[node];
            else lzya[2 * node] += lzya[node];
            if (lzys[2 * node + 1] != linf) lzys[2 * node + 1] += lzya[node];
            else lzya[2 * node + 1] += lzya[node];
        }
    }
    if (lzys[node] != linf) {
        st[node] = Node(r - l + 1, r - l + 1, r - l + 1, r - l + 1, lzys[node], lzys[node]);
        lzys[node] = linf;
    }
    if (lzya[node] != 0) {
        st[node].lval += lzya[node]; st[node].rval += lzya[node];
        lzya[node] = 0;
    }
}
void Set(int node, int l, int r, int ql, int qr, ll y) {
    Propagate(node, l, r);
    if (r < ql || qr < l || ql > qr) return;
    if (ql <= l && r <= qr) {
        lzys[node] = y;
        Propagate(node, l, r);
        return;
    }
    int mid = l + r >> 1;
    Set(2 * node, l, mid, ql, qr, y);
    Set(2 * node + 1, mid + 1, r, ql, qr, y);
    st[node] = Merge(st[2 * node], st[2 * node + 1]);
}
void Add(int node, int l, int r, int ql, int qr, ll y) {
    Propagate(node, l, r);
    if (r < ql || qr < l || ql > qr) return;
    if (ql <= l && r <= qr) {
        lzya[node] = y;
        Propagate(node, l, r);
        return;
    }
    int mid = l + r >> 1;
    Add(2 * node, l, mid, ql, qr, y);
    Add(2 * node + 1, mid + 1, r, ql, qr, y);
    st[node] = Merge(st[2 * node], st[2 * node + 1]);
}
Node Get(int node, int l, int r, int ql, int qr) {
    Propagate(node, l, r);
    if (r < ql || qr < l || ql > qr) return Node();
    if (ql <= l && r <= qr) return st[node];
    int mid = l + r >> 1;
    return Merge(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr));
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    st1.Reset1(n); st2.Reset1(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        st1.Add1(1, 1, n, i, i, a[i]);
    }
    for (int i = 1; i < n; i++) d[i] = a[i + 1] - a[i];
    if (n == 1) {
        while (q--) {
            int x; cin >> x;
            cout << 1 << en;
        }
        return 0;
    }
    Init(1, 1, n - 1);
    while (q--) {
        int ty; cin >> ty;
        if (ty == 1) {
            int l, r;
            ll s, c;
            cin >> l >> r >> s >> c;
            st1.Add1(1, 1, n, l, r, s - l * c);
            st2.Add1(1, 1, n, l, r, c);
            if (l > 1) Add(1, 1, n - 1, l - 1, l - 1, s);
            Add(1, 1, n - 1, l, r - 1, c);
            if (r < n) Add(1, 1, n - 1, r, r, -s - (r - l) * c);
        }
        else if (ty == 2) {
            int l, r;
            ll s, c;
            cin >> l >> r >> s >> c;
            st1.Set1(1, 1, n, l, r, s - l * c);
            st2.Set1(1, 1, n, l, r, c);
            if (l > 1) {
                ll val = st1.Get1(1, 1, n, l - 1) + (l - 1) * st2.Get1(1, 1, n, l - 1);
                Set(1, 1, n - 1, l - 1, l - 1, s - val);
            }
            Set(1, 1, n - 1, l, r - 1, c);
            if (r < n) {
                ll val = st1.Get1(1, 1, n, r + 1) + (r + 1) * st2.Get1(1, 1, n, r + 1);
                Set(1, 1, n - 1, r, r, val - s - (r - l) * c);
            }
        }
        else {
            int l, r;
            cin >> l >> r;
            cout << Get(1, 1, n - 1, l, r - 1).ans + 1 << en;
        }
    }
    return 0;
}

Compilation message

Progression.cpp: In member function 'void Segtree::Set1(int, int, int, int, int, long long int)':
Progression.cpp:44:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid = l + r >> 1;
      |                   ~~^~~
Progression.cpp: In member function 'void Segtree::Add1(int, int, int, int, int, long long int)':
Progression.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mid = l + r >> 1;
      |                   ~~^~~
Progression.cpp: In member function 'long long int Segtree::Get1(int, int, int, int)':
Progression.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid = l + r >> 1;
      |                   ~~^~~
Progression.cpp: In function 'void Init(int, int, int)':
Progression.cpp:99:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     int mid = l + r >> 1;
      |               ~~^~~
Progression.cpp: In function 'void Set(int, int, int, int, int, long long int)':
Progression.cpp:135:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |     int mid = l + r >> 1;
      |               ~~^~~
Progression.cpp: In function 'void Add(int, int, int, int, int, long long int)':
Progression.cpp:148:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  148 |     int mid = l + r >> 1;
      |               ~~^~~
Progression.cpp: In function 'Node Get(int, int, int, int, int)':
Progression.cpp:157:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  157 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 121684 KB Output is correct
2 Correct 96 ms 41112 KB Output is correct
3 Correct 100 ms 41164 KB Output is correct
4 Correct 96 ms 41156 KB Output is correct
5 Correct 97 ms 41228 KB Output is correct
6 Correct 95 ms 41216 KB Output is correct
7 Correct 97 ms 41160 KB Output is correct
8 Incorrect 17 ms 37864 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38100 KB Output is correct
2 Correct 18 ms 37972 KB Output is correct
3 Correct 21 ms 37900 KB Output is correct
4 Correct 22 ms 37920 KB Output is correct
5 Incorrect 17 ms 37948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 116496 KB Output is correct
2 Correct 124 ms 38464 KB Output is correct
3 Correct 102 ms 38468 KB Output is correct
4 Correct 94 ms 38576 KB Output is correct
5 Correct 125 ms 38628 KB Output is correct
6 Correct 104 ms 38608 KB Output is correct
7 Correct 122 ms 38564 KB Output is correct
8 Correct 17 ms 37948 KB Output is correct
9 Correct 17 ms 37844 KB Output is correct
10 Correct 16 ms 37852 KB Output is correct
11 Correct 392 ms 116052 KB Output is correct
12 Correct 399 ms 116484 KB Output is correct
13 Correct 419 ms 116096 KB Output is correct
14 Correct 412 ms 116140 KB Output is correct
15 Correct 408 ms 116348 KB Output is correct
16 Correct 425 ms 116724 KB Output is correct
17 Correct 401 ms 116860 KB Output is correct
18 Correct 431 ms 116720 KB Output is correct
19 Correct 374 ms 116152 KB Output is correct
20 Correct 382 ms 116104 KB Output is correct
21 Correct 382 ms 116032 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 122980 KB Output is correct
2 Correct 192 ms 41288 KB Output is correct
3 Correct 193 ms 41300 KB Output is correct
4 Correct 201 ms 41196 KB Output is correct
5 Correct 196 ms 41308 KB Output is correct
6 Correct 197 ms 41288 KB Output is correct
7 Correct 188 ms 41320 KB Output is correct
8 Incorrect 17 ms 37972 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 116496 KB Output is correct
2 Correct 124 ms 38464 KB Output is correct
3 Correct 102 ms 38468 KB Output is correct
4 Correct 94 ms 38576 KB Output is correct
5 Correct 125 ms 38628 KB Output is correct
6 Correct 104 ms 38608 KB Output is correct
7 Correct 122 ms 38564 KB Output is correct
8 Correct 17 ms 37948 KB Output is correct
9 Correct 17 ms 37844 KB Output is correct
10 Correct 16 ms 37852 KB Output is correct
11 Correct 392 ms 116052 KB Output is correct
12 Correct 399 ms 116484 KB Output is correct
13 Correct 419 ms 116096 KB Output is correct
14 Correct 412 ms 116140 KB Output is correct
15 Correct 408 ms 116348 KB Output is correct
16 Correct 425 ms 116724 KB Output is correct
17 Correct 401 ms 116860 KB Output is correct
18 Correct 431 ms 116720 KB Output is correct
19 Correct 374 ms 116152 KB Output is correct
20 Correct 382 ms 116104 KB Output is correct
21 Correct 382 ms 116032 KB Output is correct
22 Correct 1312 ms 122180 KB Output is correct
23 Correct 199 ms 41212 KB Output is correct
24 Correct 201 ms 41240 KB Output is correct
25 Correct 198 ms 41164 KB Output is correct
26 Correct 206 ms 41248 KB Output is correct
27 Correct 202 ms 41332 KB Output is correct
28 Correct 201 ms 41240 KB Output is correct
29 Incorrect 16 ms 37848 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 121684 KB Output is correct
2 Correct 96 ms 41112 KB Output is correct
3 Correct 100 ms 41164 KB Output is correct
4 Correct 96 ms 41156 KB Output is correct
5 Correct 97 ms 41228 KB Output is correct
6 Correct 95 ms 41216 KB Output is correct
7 Correct 97 ms 41160 KB Output is correct
8 Incorrect 17 ms 37864 KB Output isn't correct
9 Halted 0 ms 0 KB -