oj.uz

답안 #332883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332883 2020-12-03T23:55:29 Z 12tqian Two Antennas (JOI19_antennas) C++17
22 / 100
 638 ms 23104 KB 
#include <bits/stdc++.h>

const int INF = 1e9;

template <class T> struct LazySeg {
    int sz;
    std::vector<T> c; // stores max of c
    std::vector<T> d; // stores max of d
    std::vector<T> lazy; // stores what you subtract max with
    void init(int n) {
        sz = 1;
        while (sz < n) sz *= 2;
        c.assign(2 * sz, -INF);
        d.assign(2 * sz, -INF);
        lazy.assign(2 * sz, -INF);
    }   
    void pull(int ind) {
        c[ind] = std::max(c[2 * ind], c[2 * ind + 1]);
        d[ind] = std::max(d[2 * ind], d[2 * ind + 1]);
    }
    void push(int ind, int L, int R) {
        d[ind] = std::max(d[ind], c[ind] + lazy[ind]);
        if (L != R) {
            lazy[2 * ind] = std::max(lazy[2 * ind], lazy[ind]);
            lazy[2 * ind + 1] = std::max(lazy[2 * ind + 1], lazy[ind]);
        }
        lazy[ind] = -INF;
    }
    void set(int p, T val, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;   
        push(ind, L, R);
        if (p < L || R < p) return; 
        if (L == R) {
            c[ind] = val;
            return;
        }
        int M = (L + R) / 2;
        set(p, val, 2 * ind, L, M);
        set(p, val, 2 * ind + 1, M + 1, R);
        pull(ind);
    }
    void set_max(int lo, int hi, T val, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);
        if (R < lo || hi < L) return;
        if (lo <= L && R <= hi) {
            lazy[ind] = val;
            return;
        }
        int M = (L + R) / 2;
        set_max(lo, hi, val, 2 * ind, L, M);
        set_max(lo, hi, val, 2 * ind + 1, M + 1, R);
        pull(ind);
    }
    T qmax(int t, int lo, int hi, int ind = 1, int L = 0, int R = -1) {
        if (R == -1) R += sz;
        push(ind, L, R);    
        if (R < lo || hi < L) return -INF;
        if (lo <= L && R <= hi) return (t == 0 ? c[ind] : d[ind]);
        int M = (L + R) / 2;
        return std::max(qmax(t, lo, hi, 2 * ind, L, M), qmax(t, lo, hi, 2 * ind + 1, M + 1, R));
    }
};

int main() {
    using namespace std;
    ios_base::sync_with_stdio(0);
    int n; cin >> n;
    vector<int> h(n), a(n), b(n);
    for (int i = 0; i < n; i++) 
        cin >> h[i] >> a[i] >> b[i];
    int q; cin >> q;
    vector<array<int, 2>> queries(q);
    for (int i = 0; i < q; i++)
        cin >> queries[i][0] >> queries[i][1], queries[i][0]--, queries[i][1]--;
    vector<int> ans(q, -1);
    LazySeg<int> seg;
    int tt = 0;
    auto solve = [&]() {
        tt++;
        seg.init(n);
        vector<vector<array<int, 2>>> events(n);
        for (int i = 0; i < n; i++) {
            if (i + a[i] < n)
                events[i + a[i]].push_back({1, i});
            if (i + b[i] < n)
                events[i + b[i]].push_back({3, i});
            events[i].push_back({2, i});
        }
        for (int i = 0; i < q; i++) 
            events[queries[i][1]].push_back({4, i});
        for (auto& v : events)
            sort(v.begin(), v.end());        
        for (int j = 0; j < n; j++) {
            for (auto& e : events[j]) {
                int id = e[1];
                if (e[0] == 1) {
                    seg.set(id, h[id]);
                } else if (e[0] == 2) {
                    int l = max(0, j - b[id]);
                    int r = j - a[id];
                    if (l <= r) {
                        seg.set_max(l, r, -h[id]);
                    }
                } else if (e[0] == 3) {
                    seg.set(id, -INF);
                } else if (e[0] == 4) {
                    int l = queries[id][0];
                    int r = queries[id][1];
                    ans[id] = max(ans[id], seg.qmax(1, l, r));
                }
            }
        }
    };
    solve();
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    reverse(h.begin(), h.end());
    for (int i = 0; i < q; i++) {
        queries[i][0] = n - 1 - queries[i][0];
        queries[i][1] = n - 1 - queries[i][1];
        swap(queries[i][0], queries[i][1]);
    }
    solve();
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';
    return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 540 ms 20076 KB Output is correct
2 Correct 621 ms 21612 KB Output is correct
3 Correct 397 ms 17416 KB Output is correct
4 Correct 638 ms 21672 KB Output is correct
5 Correct 234 ms 10944 KB Output is correct
6 Correct 632 ms 21612 KB Output is correct
7 Correct 525 ms 19692 KB Output is correct
8 Correct 623 ms 21524 KB Output is correct
9 Correct 66 ms 4076 KB Output is correct
10 Correct 635 ms 21580 KB Output is correct
11 Correct 340 ms 13292 KB Output is correct
12 Correct 627 ms 21652 KB Output is correct
13 Correct 538 ms 22912 KB Output is correct
14 Correct 513 ms 22920 KB Output is correct
15 Correct 480 ms 22944 KB Output is correct
16 Correct 484 ms 22876 KB Output is correct
17 Correct 555 ms 22880 KB Output is correct
18 Correct 548 ms 22864 KB Output is correct
19 Correct 518 ms 22936 KB Output is correct
20 Correct 510 ms 22800 KB Output is correct
21 Correct 499 ms 23104 KB Output is correct
22 Correct 512 ms 22940 KB Output is correct
23 Correct 505 ms 22944 KB Output is correct
24 Correct 477 ms 23100 KB Output is correct

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -