Submission #1132137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132137		antonn	Fire (JOI20_ho_t5)	C++20	100 / 100	467 ms	128784 KiB

ho_t5

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 2e5+7;
const int L = 20;

int a[N], t[L][N], lg[N]; 
vector<array<int, 4>> v;
vector<pair<int, int>> qs[N], add[N];

int get_max(int l, int r) {
    int p = lg[r - l + 1];
    return max(t[p][l], t[p][r - (1 << p) + 1]);
}

ll get(int t, int x) {
    ll ans = 0;
    for (auto [l, r, pos, val] : v) {
        if (l <= t && t <= r && pos <= x) {
            ans += val;
        }
    }
    return ans;
}

ll f[N];

void inc(int i, int x) {
    for (; i < N; i += i & -i) f[i] += x;
}

ll get(int i) {
    ll res = 0;
    for (; i >= 1; i -= i & -i) res += f[i];
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    for (int i = 1; i <= n; ++i) t[0][i] = a[i];
    for (int h = 1; h < L; ++h) {
        for (int i = 1; i + (1 << h) - 1 <= n; ++i) {
            t[h][i] = max(t[h - 1][i], t[h - 1][i + (1 << (h - 1))]);
        }
    }
    for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1; 
    
    for (int i = 1; i <= n; ++i) {
        int t = 1;
        while (true) {
            int cur = get_max(max(1, i - t), i);
            int l = t, r = n;
            while (l <= r) {
                int m = (l + r) / 2;
                if (get_max(max(1, i - m), i) == cur) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            v.push_back({t, l - 1, i, cur});
            if (l == n + 1) break;
            t = l;
        }
    }
    
    for (int i = 1; i <= q; ++i) {
        int t, l, r; cin >> t >> l >> r;
        qs[t].push_back({r, i});
        qs[t].push_back({l - 1, -i});
    }
    for (auto [l, r, pos, val] : v) {
        add[l].push_back({pos, val});
        add[r + 1].push_back({pos, -val});
    }
    vector<ll> sol(q + 1);
    for (int t = 1; t <= n; ++t) {
        for (auto [pos, val] : add[t]) {
            inc(pos, val);
        }
        for (auto [pos, i] : qs[t]) {
            if (i > 0) sol[i] += get(pos);
            if (i < 0) sol[-i] -= get(pos);
        }
    }
    for (int i = 1; i <= q; ++i) cout << sol[i] << "\n";
}

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