Submission #1131871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131871		antonn	Fire (JOI20_ho_t5)	C++20	1 / 100	91 ms	159304 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; }

#define int ll

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

int n, a[N], q, lg[N];
vector<int> g[N];
pair<int, int> rmq[L][N];
vector<array<int, 3>> small[K];
int anc[L][N], mx[L][N], dep[N];
ll sum[L][N], b[N], pref[N], sol[N];

pair<int, int> join(pair<int, int> a, pair<int, int> b) {
    if (a.first > b.first) {
        return a;
    } else if (a.first == b.first) {
        return a.second < b.second ? a : b;
    } else {
        return b;
    }
}

void dfs(int u) {
    for (auto v : g[u]) {
        dep[v] = dep[u] + 1;
        anc[0][v] = u;
        sum[0][v] = a[v] * (u - v);
        mx[0][v] = u - v;
        dfs(v);
    }
}

int get_val_max(int l, int r) {
    int p = lg[r - l + 1];
    return max(rmq[p][l], rmq[p][r - (1 << p) + 1]).first;
}

int get_pos_max(int l, int r) {
    int p = lg[r - l + 1];
    return max(rmq[p][l], rmq[p][r - (1 << p) + 1]).second;
}

int get_first_bigger(int pos, int t) {
    for (int h = L - 1; h >= 0; --h) {
        if (mx[h][pos] <= t) {
            pos = anc[h][pos];
        }
    }
    return pos;
}

int lift(int x, int k) {
    for (int h = L - 1; h >= 0; --h) {
        if (k & (1 << h)) {
            x = anc[h][x];
        }
    }
    return x;
}

int get_before(int x, int y) {
    if (x == y) return x;
    return lift(x, dep[x] - dep[y] - 1);
}

ll get_sum(int a, int b) {
    ll ans = 0;
    for (int h = L - 1; h >= 0; --h) {
        if (dep[a] - (1 << h) >= dep[b]) {
            ans += sum[h][a];
            a = anc[h][a];
        }
    }
    return ans;
}

int get_until(int pos, int x) {
    for (int h = L - 1; h >= 0; --h) {
        if (anc[h][pos] <= x) {
            pos = anc[h][pos];
        }
    }
    return pos;
}

int brute(int x, int t) {
    while (anc[0][x] != 0 && anc[0][x] - x > t) {
        x = anc[0][x];
    }
    return x;
}

ll get(int t, int x) { // s(t)[1] + s(t)[2] + ... + s(t)[x]
    int pos = 1;
    ll ans = 0;
    while (pos <= x) {
        int last = get_first_bigger(pos, t);
        assert(last == brute(pos, t));
        // cout << "! " << pos << " " << last << "\n";
        if (last <= x) {
            ans += get_sum(pos, last);
            if (last + t >= x) {
                ans += a[last] * (x - last + 1);
                break;
            }
            ans += a[last] * (t + 1);
            pos = get_pos_max(last + 1, min(n, last + t + 1));
            ans -= ((last + t) - pos + 1) * a[pos];
        } else {
            int stop = get_until(pos, x);
            ans += get_sum(pos, stop);
            ans += a[stop] * (x - stop + 1); 
            break;
        }
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    for (int i = 1; i <= n; ++i) rmq[0][i] = {a[i], i};
    for (int h = 1; h < L; ++h) {
        for (int i = 1; i + (1 << h) - 1 <= n; ++i) {
            rmq[h][i] = join(rmq[h - 1][i], rmq[h - 1][i + (1 << (h - 1))]);
        }
    }
    for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
    
    vector<int> lft(n + 1), rgh(n + 1);
    vector<int> stk;
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && a[i] >= a[stk.back()]) stk.pop_back();
        if (stk.empty()) lft[i] = -1e9;
        if (!stk.empty()) lft[i] = stk.back() + 1;
        stk.push_back(i);
    }
    stk.clear();
    for (int i = n; i >= 1; --i) {
        while (!stk.empty() && a[i] >= a[stk.back()]) stk.pop_back();
        if (stk.empty()) rgh[i] = +1e9;
        if (!stk.empty()) rgh[i] = stk.back();
        stk.push_back(i);
    }
    
    for (int i = 1; i <= n; ++i) if (rgh[i] != 1e9) g[rgh[i]].push_back(i);
    for (int i = 1; i <= n; ++i) if (rgh[i] == 1e9) mx[0][i] = 1e9, dfs(i);
    
    for (int h = 1; h < L; ++h) {
        for (int i = 1; i <= n; ++i) {
            anc[h][i] = anc[h - 1][anc[h - 1][i]];
            mx[h][i] = max(mx[h - 1][i], mx[h - 1][anc[h - 1][i]]);
            sum[h][i] = sum[h - 1][i] + sum[h - 1][anc[h - 1][i]];
        }
    }
    
    for (int i = 1; i <= q; ++i) {
        int t, l, r; cin >> t >> l >> r;
        // cout << "! " << get(t, r) - get(t, l - 1) << "\n";
        if (t > K) {
            sol[i] = get(t, r) - get(t, l - 1);
        } else {
            small[t].push_back({l, r, i});
        }
    }
    for (int t = 1; t < K; ++t) {
        for (int i = 1; i <= n; ++i) b[i] = get_val_max(max(1LL, i - t), i);
        for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + b[i];
        for (auto [l, r, i] : small[t]) sol[i] = pref[r] - pref[l - 1];
    }
    for (int i = 1; i <= q; ++i) cout << sol[i] << "\n";
}

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