Submission #1115467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115467		Zero_OP	Fire (JOI20_ho_t5)	C++14	100 / 100	285 ms	56752 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;

#define dbg(x) "[" << #x << " = " << (x) << "]"

enum event_type {
    start_decreasing, stop_increasing, become_zero
};

struct fenwick_tree{
    vector<long long> bit;
    fenwick_tree(int n) : bit(n + 1, 0) {}

    void update(int id, long long val){
        for(; id < (int)bit.size(); id += id & (-id)) bit[id] += val;
    }

    long long query(int id){
        long long sum = 0;
        for(; id > 0; id -= id & (-id)) sum += bit[id];
        return sum;
    }

    void debug(){
        cout << "[";
        for(int i = 1; i < (int)bit.size(); ++i){
            cout << query(i) - query(i - 1);
            if(i + 1 == (int)bit.size()) cout << "]\n";
            else cout << ", ";
        }
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, Q;
    cin >> N >> Q;
    vector<int> S(N + 1), L(N + 1), R(N + 1), stop_inc(N + 1), start_dec(N + 1);
    stack<int> st;

    for(int i = 1; i <= N; ++i){
        cin >> S[i];
    }

    for(int i = 1; i <= N; ++i){
        while(!st.empty() && S[st.top()] <= S[i]) st.pop();
        L[i] = (st.empty() ? -(2 * N + 1) : st.top());
        st.push(i);
    }

    while(!st.empty()) st.pop();
    for(int i = N; i >= 1; --i){
        while(!st.empty() && S[st.top()] < S[i]) st.pop();
        R[i] = (st.empty() ? + (N + 1) : st.top());
        st.push(i);
    }

//    for(int i = 1; i <= N; ++i){
//        cout << "LR : " << i << " " << L[i] << ' ' << R[i] << '\n';
//    }


/*
    - Consider frequency table on ranges
    Event :
    Part 1 : Start increasing
    Part 2, 3 : (i - L[i]) : Start decreasing, (R[i] - i) : Stop increasing (May be 3, 2 or 2, 3)
    Part 4 : (R[i] - L[i] - 1) Become zero when the first S[j] larger than S[i] reach the stop-increasing point

    the points for S[i] after T (remember to plus 1) is
    f(i, S) = max(0, S[i] * min(T, stop_inc[i]) - S[i] * max(0, T - start_dec[i]))

    For T - start_dec[i] >= 0 => T >= start_dec[i], we can calculate this part by let S[i] * T * cnt_on - S[i] * sum start_dec[pos]

    ok now we have to handle the case for this equation :
            min(T, stop_inc[i]) >= max(0, T - start_dec[i])

    consider when T < stop_inc[i] => T >= max(0, T - start_dec[i]) <=> T >= T - start_dec[i] (ez)
    consider when T > stop_inc[i] => stop_inc[i] >= max(0, T - start_dec[i]) <=> stop_inc[i] >= T - start_dec[i] <=> stop_inc[i] + start_dec[i] >= T
*/

    vector<vector<tuple<int, int, int>>> queries(N + 2);
    for(int i = 0; i < Q; ++i){
        int t, l, r;
        cin >> t >> l >> r;
        queries[t + 1].emplace_back(l, r, i);
    }

    vector<vector<tuple<event_type, int>>> sweep(N + 2);

    for(int i = 1; i <= N; ++i){
        { //start decreasing
            int t = i - L[i];
            start_dec[i] = t;
            if(1 <= t && t <= N + 1){
                sweep[t].emplace_back(start_decreasing, i);
            }
        }

        { //stop increasing
            int t = R[i] - i;
            stop_inc[i] = t;
            if(1 <= t && t <= N + 1){
                sweep[t].emplace_back(stop_increasing, i);
            }
        }

        { //become zero
            int t = start_dec[i] + stop_inc[i] - 1;
//            cout << "become zero : " << i << " -> " << t << '\n';
            if(1 <= t && t <= N + 1){
                sweep[t].emplace_back(become_zero, i);
            }
        }

//        cout << i << "(" << start_dec[i] << ", " << stop_inc[i] << ")\n";
    }

//    cout << '\n';

    int B = 32 - __builtin_clz(N);
    vector<vector<int>> prev(B, vector<int>(N + 1, -1));

    for(int i = 1; i <= N; ++i){
        prev[0][i] = L[i];
    }

    for(int i = 1; i < B; ++i){
        for(int j = 1; j <= N; ++j){
            prev[i][j] = prev[i - 1][j];
            if(prev[i][j] > 0) prev[i][j] = prev[i - 1][prev[i][j]];
        }
    }

    auto find_exact_value = [&](int i, int t) -> int{
        int cur = i;
        for(int b = B - 1; b >= 0; --b){
            if(prev[b][cur] > 0 && i - prev[b][cur] <= t){
                cur = prev[b][cur];
            }
        }
        return cur;
    };

//    vector<long long> answer(Q);
//    for(int t = 2; t <= N + 1; ++t){
//        long long sum = 0;
//        for(auto [l, r, id] : queries[t]){
//            long long sum = 0;
//            for(int i = l; i <= r; ++i){
//                cout << max(0, S[i] * (min(t, stop_inc[i]) - max(0, t - start_dec[i]))) << ' ';
//                sum += max(0, S[i] * (min(t, stop_inc[i]) - max(0, t - start_dec[i])));
//            }
//
//            answer[id] = sum;
//        }
//    }
//
//    for(int i = 0; i < Q; ++i) cout << answer[i] << '\n';

    fenwick_tree ft1(N), ft2(N), ft3(N), ft4(N);

    for(int i = 1; i <= N; ++i){
        ft1.update(i, S[i]);
    }

    vector<long long> answer(Q);
    for(int t = 1; t <= N + 1; ++t){
//        cout << "at : " << t << '\n';

        auto calculate_prefix = [&](int r) -> long long{
//            cout << dbg(r) << ' ';
            int pos = find_exact_value(r, t - 1);
//            cout << dbg(pos) << ' ';

            long long A = ft1.query(pos - 1);
            long long B = ft2.query(pos - 1);
            long long C = ft3.query(pos - 1);
            long long D = ft4.query(pos - 1);

            long long sum_part = A * t + B;
            long long loss_part = D * t - C;
            int num_inc = L[pos] + t;
            long long extra_part = 1LL * S[pos] * (r - max(pos, num_inc) + 1);
            assert(extra_part >= 0);
//            cout << dbg(sum_part) << dbg(loss_part) << dbg(extra_part) << '\n';
//            cout << dbg(A) << dbg(B) << dbg(C) << dbg(D) << '\n';
//            cout << dbg(sum_part - loss_part + extra_part) << '\n' << '\n';
            return sum_part - loss_part + extra_part;
        };

        for(auto [l, r, i] : queries[t]){
            answer[i] = calculate_prefix(r) - (l > 1 ? calculate_prefix(l - 1) : 0);
        }

        for(auto [e, i] : sweep[t]){
            if(e == start_decreasing){
//                cout << "start decreasing : " << i << '\n';
                ft3.update(i, 1LL * S[i] * start_dec[i]);
                ft4.update(i, S[i]);
            } else if(e == stop_increasing){
//                cout << "stop increasing : " << i << '\n';
                ft1.update(i, -S[i]);
                ft2.update(i, 1LL * S[i] * stop_inc[i]);
            } else if(e == become_zero){
//                cout << "become zero : " << i << '\n';
                ft2.update(i, -1LL * S[i] * stop_inc[i]);
                ft3.update(i, -1LL * S[i] * start_dec[i]);
                ft4.update(i, -S[i]);
            } else assert(false);
        }

//        cout << '\n';
//        cout << "that's all\n\n";
    }

    for(int i = 0; i < Q; ++i){
        cout << answer[i] << '\n';
    }

    return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:200:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  200 |         for(auto [l, r, i] : queries[t]){
      |                  ^
ho_t5.cpp:204:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  204 |         for(auto [e, i] : sweep[t]){
      |                  ^

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80