Submission #1115468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115468		Zero_OP	Fire (JOI20_ho_t5)	C++14	100 / 100	276 ms	50876 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;

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;
    }
};

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

    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);
    }

    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;
            if(1 <= t && t <= N + 1){
                sweep[t].emplace_back(become_zero, i);
            }
        }
    }

    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;
    };

    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){
        auto calculate_prefix = [&](int r) -> long long{
            int pos = find_exact_value(r, t - 1);

            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);
            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){
                ft3.update(i, 1LL * S[i] * start_dec[i]);
                ft4.update(i, S[i]);
            } else if(e == stop_increasing){
                ft1.update(i, -S[i]);
                ft2.update(i, 1LL * S[i] * stop_inc[i]);
            } else if(e == become_zero){
                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);
        }
    }

    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:131:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  131 |         for(auto [l, r, i] : queries[t]){
      |                  ^
ho_t5.cpp:135:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  135 |         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