oj.uz

Submission #602351

# Submission time Handle Problem Language Result Execution time Memory
602351 2022-07-22T23:37:12 Z verngutz Progression (NOI20_progression) C++17
35 / 100
 3000 ms 44108 KB 
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
vector<ll> a;
struct segtree {
    segtree* l;
    segtree* r;
    int L, R;
    ll delta;
    int longest_suff, longest_pref, longest, longest_start_index;
    segtree(int L, int R): L(L), R(R), delta(0) {
        if(R - L > 1) {
            int M = (L + R) / 2;
            l = new segtree(L, M);
            r = new segtree(M, R);
        } else {
            l = nullptr;
            r = nullptr;
        }
    }
    void combine() {
        int M = (L + R) / 2;
        longest_suff = r->longest_suff;
        if(r->longest_suff == r->len() && l->back() == r->front()) {
            longest_suff += l->longest_suff;
        }
        longest_pref = l->longest_pref;
        if(l->longest_pref == l->len() && l->back() == r->front()) {
            longest_pref += r->longest_pref;
        }
        int crossing = l->back() == r->front() ? l->longest_suff + r->longest_pref : 0;
        longest = max({l->longest, r->longest, crossing});
        if(longest == r->longest) {
            longest_start_index = r->longest_start_index;
        } else if(longest == crossing) {
            longest_start_index = M - l->longest_suff;
        } else {
            longest_start_index = l->longest_start_index;
        }
    }
    void build() {
        delta = 0;
        if(R - L > 1) {
            r->build();
            l->build();
            combine();
        } else {
            longest_suff = 1;
            longest_pref = 1;
            longest = 1;
            longest_start_index = L;
        }
    }
    ll front() {
        if(delta == 0 and l != nullptr) {
            return l->front();
        } else {
            return a[L] + delta;
        }
    }
    ll back() {
        if(delta == 0 and r != nullptr) {
            return r->back();
        } else {
            return a[R - 1] + delta;
        }
    }
    int len() {
        return R - L;
    }
    pair<int, int> query(int s, int e) {
        if(s <= L and R <= e) {
            return {longest, longest_start_index};
        } else if(R <= s or e <= L) {
            return {0, -1};
        } else {
            int M = (L + R) / 2;
            auto [L_longest, L_start_index] = l->query(s, e);
            auto [R_longest, R_start_index] = r->query(s, e);
            int crossing = l->back() == r->front() 
                ? min(l->longest_suff, M - s) + min(r->longest_pref, e - M)
                : 0;
            int crossing_start_index = l->back() == r->front() 
                ? max(M - l->longest_suff, s)
                : -1;
            int ans = max({L_longest, R_longest, crossing});
            int index;
            if(ans == R_longest) {
                index = R_start_index;
            } else if(ans == crossing) {
                index = crossing_start_index;
            } else {
                index = max(L_start_index, s);
            }
            return {ans, index};
        }
    }
    void increment(int s, int e, int x) {
        if(s <= L and R <= e) {
            delta += x;
        } else if(R <= s or e <= L) {
            return;
        } else {
            if(delta != 0) {
                l->delta += delta;
                r->delta += delta;
                delta = 0;
            }
            l->increment(s, e, x);
            r->increment(s, e, x);
            combine();
        }
    }
    ~segtree() {
        delete l;
        delete r;
    }
    void print() {
        if(R - L > 1) {
            if(delta == 0) {
                l->print();
                r->print();
            } else {
                for(int i = L; i < R; i++) {
                    cerr << a[i] + delta << " ";
                }
            }
        } else {
            cerr << a[L] + delta << " ";
        }
    }
    void debug(int depth = 0) {
        for(int i = 0; i < depth; i++) {
            cerr << "\t";
        }
        err(L, R, delta, longest, longest_pref, longest_suff, back(), front());
        if(R - L > 1) {
            l->debug(depth + 1);
            r->debug(depth + 1);
        }
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<ll> d(n);
    cin >> d;
    a.resize(n);
    adjacent_difference(d.begin(), d.end(), a.begin());
    segtree st(0, n);
    st.build();
    while(q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int L, R, S, C;
            cin >> L >> R >> S >> C;
            L--, R--;
            st.increment(L, L + 1, S);
            if(R + 1 < n) {
                st.increment(R + 1, R + 2, -S);
            }
            st.increment(L + 1, R + 1, C);
            if(R + 1 < n) {
                st.increment(R + 1, R + 2, (R - L) * -C);
            }
        } else if(t == 2) {
            int L, R, S, C;
            cin >> L >> R >> S >> C;
            L--, R--;
            for(int i = L; i <= R; i++) {
                d[i] = S + (i - L) * C;
            }
            adjacent_difference(d.begin(), d.end(), a.begin());
            st.build();
        } else {
            int L, R;
            cin >> L >> R;
            L--, R--;
            auto [longest, longest_start_index] = st.query(L, R + 1);
            cout << longest + (longest_start_index != L) << endl;
        }
    }
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 42828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1649 ms 43712 KB Output is correct
2 Correct 458 ms 880 KB Output is correct
3 Correct 453 ms 900 KB Output is correct
4 Correct 452 ms 872 KB Output is correct
5 Correct 438 ms 1288 KB Output is correct
6 Correct 465 ms 884 KB Output is correct
7 Correct 459 ms 1068 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 2176 ms 43600 KB Output is correct
12 Correct 1612 ms 43644 KB Output is correct
13 Correct 2154 ms 43424 KB Output is correct
14 Correct 2179 ms 43472 KB Output is correct
15 Correct 1588 ms 43828 KB Output is correct
16 Correct 2193 ms 43904 KB Output is correct
17 Correct 2068 ms 43920 KB Output is correct
18 Correct 2071 ms 44108 KB Output is correct
19 Correct 1707 ms 43416 KB Output is correct
20 Correct 1848 ms 43416 KB Output is correct
21 Correct 1708 ms 43468 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3097 ms 42488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1649 ms 43712 KB Output is correct
2 Correct 458 ms 880 KB Output is correct
3 Correct 453 ms 900 KB Output is correct
4 Correct 452 ms 872 KB Output is correct
5 Correct 438 ms 1288 KB Output is correct
6 Correct 465 ms 884 KB Output is correct
7 Correct 459 ms 1068 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 2176 ms 43600 KB Output is correct
12 Correct 1612 ms 43644 KB Output is correct
13 Correct 2154 ms 43424 KB Output is correct
14 Correct 2179 ms 43472 KB Output is correct
15 Correct 1588 ms 43828 KB Output is correct
16 Correct 2193 ms 43904 KB Output is correct
17 Correct 2068 ms 43920 KB Output is correct
18 Correct 2071 ms 44108 KB Output is correct
19 Correct 1707 ms 43416 KB Output is correct
20 Correct 1848 ms 43416 KB Output is correct
21 Correct 1708 ms 43468 KB Output is correct
22 Incorrect 1370 ms 42972 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3078 ms 42828 KB Time limit exceeded
2 Halted 0 ms 0 KB -