Submission #386578

#	Time	Username	Problem	Language	Result	Execution time	Memory
386578		timmyfeng	Dungeon 3 (JOI21_ho_t5)	C++17	100 / 100	1242 ms	140384 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 200001;
const int L = __lg(N) + 1;

struct segtree {
    segtree *left, *right;
    long long sum, lazy, count;

    segtree(int l, int r, long long *a) {
        lazy = 0;
        if (l + 1 == r) {
            count = a[l + 1] - a[l];
            sum = 0;
        } else {
            int m = (l + r) / 2;
            left = new segtree(l, m, a);
            right = new segtree(m, r, a);
            pull();
        }
    }

    void apply(long long x) {
        sum += count * x, lazy += x;
    }

    void pull() {
        sum = left->sum + right->sum;
        count = left->count + right->count;
    }

    void push() {
        if (lazy != 0) {
            left->apply(lazy);
            right->apply(lazy);
            lazy = 0;
        }
    }

    void update(int a, int b, long long x, int l, int r) {
        if (a == b || b <= l || r <= a) {
            return;
        } else if (a <= l && r <= b) {
            apply(x);
        } else {
            push();
            int m = (l + r) / 2;
            left->update(a, b, x, l, m);
            right->update(a, b, x, m, r);
            pull();
        }
    }

    long long query(int a, int b, int l, int r) {
        if (a == b || b <= l || r <= a) {
            return 0;
        } else if (a <= l && r <= b) {
            return sum;
        } else {
            push();
            int m = (l + r) / 2;
            return left->query(a, b, l, m) + right->query(a, b, m, r);
        }
    }
};

int max_a[L][N], b[N], nxt[N], prv[N], k;
long long a[N], ans[N], values[6 * N];
array<int, 2> min_b[L][N];

vector<array<long long, 3>> updates[N];
vector<array<int, 3>> queries[N];

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

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        max_a[0][i] = a[i];
    }

    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        min_b[0][i] = {b[i], i};
    }

    for (int i = 1; i <= __lg(n); ++i) {
        for (int j = 0; j + (1 << i) <= n; ++j) {
            max_a[i][j] = max(max_a[i - 1][j], max_a[i - 1][j + (1 << (i - 1))]);
            min_b[i][j] = min(min_b[i - 1][j], min_b[i - 1][j + (1 << (i - 1))]);
        }
    }

    partial_sum(a, a + n, a);
    rotate(a, a + n, a + n + 1);

    for (int i = 0; i < m; ++i) {
        int s, t, u;
        cin >> s >> t >> u;
        --s, --t;

        int l = __lg(t - s);

        if (max(max_a[l][s], max_a[l][t - (1 << l)]) <= u) {
            int v = lower_bound(a + s, a + t, a[t] - u) - a;
            l = __lg(t - v);
            v = min(min_b[l][v], min_b[l][t - (1 << l)])[1];
            ans[i] = (a[t] - a[v]) * b[v];
            queries[s].push_back({u, 1, i});
            queries[v].push_back({u, -1, i});
        } else {
            ans[i] = -1;
        }
    }

    vector<int> stack;
    for (int i = 0; i < n; ++i) {
        while (!stack.empty() && b[stack.back()] > b[i]) {
            nxt[stack.back()] = i;
            stack.pop_back();
        }
        prv[i] = stack.empty() ? -1 : stack.back();
        stack.push_back(i);
    }
    for (auto i : stack) {
        nxt[i] = n;
    }

    for (int i = n - 1; i >= 0; --i) {
        updates[i].push_back({0, a[nxt[i]] - a[i], b[i]});
        if (prv[i] >= 0) {
            updates[prv[i]].push_back({a[i] - a[prv[i]], a[nxt[i]] - a[prv[i]], -b[i]});
        }

        for (auto &j : updates[i]) {
            values[k++] = j[0], values[k++] = j[1];
        }

        for (auto &j : queries[i]) {
            values[k++] = j[0];
        }
    }

    sort(values, values + k);
    k = unique(values, values + k) - values;

    segtree *sum = new segtree(0, k, values);

    for (int i = n - 1; i >= 0; --i) {
        for (auto [l, r, x] : updates[i]) {
            l = lower_bound(values, values + k, l) - values;
            r = lower_bound(values, values + k, r) - values;
            sum->update(l, r, x, 0, k);
        }

        for (auto [u, t, j] : queries[i]) {
            u = lower_bound(values, values + k, u) - values;
            ans[j] += t * sum->query(0, u, 0, k);
        }
    }

    for (int i = 0; i < m; ++i) {
        cout << ans[i] << "\n";
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44