oj.uz

Submission #386576

# Submission time Handle Problem Language Result Execution time Memory
386576 2021-04-07T00:19:07 Z timmyfeng Dungeon 3 (JOI21_ho_t5) C++17
11 / 100
 1222 ms 120944 KB 
#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[4 * 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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 11756 KB Output is correct
2 Correct 17 ms 11756 KB Output is correct
3 Correct 14 ms 11244 KB Output is correct
4 Correct 17 ms 11756 KB Output is correct
5 Correct 17 ms 11756 KB Output is correct
6 Correct 14 ms 11372 KB Output is correct
7 Correct 17 ms 11628 KB Output is correct
8 Correct 17 ms 11756 KB Output is correct
9 Correct 14 ms 11244 KB Output is correct
10 Correct 18 ms 11700 KB Output is correct
11 Correct 17 ms 11776 KB Output is correct
12 Correct 14 ms 11372 KB Output is correct
13 Correct 17 ms 11756 KB Output is correct
14 Correct 16 ms 11628 KB Output is correct
15 Correct 15 ms 11628 KB Output is correct
16 Correct 17 ms 11756 KB Output is correct
17 Correct 15 ms 11244 KB Output is correct
18 Correct 15 ms 11372 KB Output is correct
19 Correct 13 ms 10988 KB Output is correct
20 Correct 17 ms 11244 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 37996 KB Output is correct
2 Correct 168 ms 38180 KB Output is correct
3 Correct 176 ms 38888 KB Output is correct
4 Correct 134 ms 31340 KB Output is correct
5 Correct 211 ms 38252 KB Output is correct
6 Incorrect 649 ms 117584 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1222 ms 120944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 11756 KB Output is correct
2 Correct 17 ms 11756 KB Output is correct
3 Correct 14 ms 11244 KB Output is correct
4 Correct 17 ms 11756 KB Output is correct
5 Correct 17 ms 11756 KB Output is correct
6 Correct 14 ms 11372 KB Output is correct
7 Correct 17 ms 11628 KB Output is correct
8 Correct 17 ms 11756 KB Output is correct
9 Correct 14 ms 11244 KB Output is correct
10 Correct 18 ms 11700 KB Output is correct
11 Correct 17 ms 11776 KB Output is correct
12 Correct 14 ms 11372 KB Output is correct
13 Correct 17 ms 11756 KB Output is correct
14 Correct 16 ms 11628 KB Output is correct
15 Correct 15 ms 11628 KB Output is correct
16 Correct 17 ms 11756 KB Output is correct
17 Correct 15 ms 11244 KB Output is correct
18 Correct 15 ms 11372 KB Output is correct
19 Correct 13 ms 10988 KB Output is correct
20 Correct 17 ms 11244 KB Output is correct
21 Correct 140 ms 37996 KB Output is correct
22 Correct 168 ms 38180 KB Output is correct
23 Correct 176 ms 38888 KB Output is correct
24 Correct 134 ms 31340 KB Output is correct
25 Correct 211 ms 38252 KB Output is correct
26 Incorrect 649 ms 117584 KB Output isn't correct
27 Halted 0 ms 0 KB -