oj.uz

답안 #570173

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
570173 2022-05-28T20:02:04 Z timreizin Two Antennas (JOI19_antennas) C++17
0 / 100
 612 ms 56528 KB 
#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <set>
#include <array>
#include <algorithm>

using namespace std;

using ll = long long;

const ll INF = 1e15;

struct segtree
{
    int n;
    vector<ll> mx, mod, tree;
    
    void push(int v)
    {
        if (mod[v] != 0)
        {
            mod[v << 1] = max(mod[v << 1], mod[v]);
            mod[v << 1 | 1] = max(mod[v << 1 | 1], mod[v]);
            tree[v << 1] = max(tree[v << 1], mx[v << 1] + mod[v]);
            tree[v << 1 | 1] = max(tree[v << 1 | 1], mx[v << 1 | 1] + mod[v]);
            mod[v] = 0;
        }
    }
    
    segtree(int n) : n(n)
    {
        mx.resize(4 * n, -INF);
        mod.resize(4 * n, 0);
        tree.resize(4 * n, -INF);
    }
    
    ll get(int a, int b, int l, int r, int v)
    {
        if (a > r || b < l) return -INF;
        if (a == l && b == r) return tree[v];
        int m = (l + r) >> 1;
        push(v);
        return max(get(a, min(b, m), l, m, v << 1), get(max(a, m + 1), b, m + 1, r, v << 1 | 1));
    }
    
    ll get(int a, int b)
    {
        return get(a, b, 0, n - 1, 1);
    }
    
    void updateH(int p, ll val, int l, int r, int v)
    {
        if (l > r) return;
        if (l == r)
        {
            mx[v] = val;
            tree[v] = val;
            return;
        }
        int m = (l + r) >> 1;
        push(v);
        if (p <= m) updateH(p, val, l, m, v << 1);
        else updateH(p, val, m + 1, r, v << 1 | 1);
        tree[v] = max(tree[v << 1], tree[v << 1 | 1]);
        mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    }
    
    void updateH(int p, ll val)
    {
        updateH(p, val, 0, n - 1, 1);
    }
    
    void updateM(int a, int b, ll val, int l, int r, int v)
    {
        if (a > r || b < l) return;
        if (a == l && b == r)
        {
            mod[v] = max(mod[v], val);
            tree[v] = max(tree[v], mx[v] + mod[v]);
            return;
        }
        int m = (l + r) >> 1;
        push(v);
        updateM(a, min(b, m), val, l, m, v << 1);
        updateM(max(a, m + 1), b, val, m + 1, r, v << 1 | 1);
        tree[v] = max(tree[v << 1], tree[v << 1 | 1]);
        mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    }
    
    void updateM(int a, int b, ll val)
    {
        updateM(a, b, val, 0, n - 1, 1);
    }
    
};

class SegmentTree
{
private:
    
    int amount;
    vector<ll> tree;
    vector<ll> mod;
    
    void push(int l, int r, int v)
    {
    }
    
    ll get(int a, int b, int l, int r, int v)
    {
        if (a > r || b < l) return -1ll;
        if (a == l && b == r) return tree[v];
        push(l, r, v);
        int m = (l + r) >> 1;
        return max(get(a, min(b, m), l, m, v << 1), get(max(a, m + 1), b, m + 1, r, (v << 1) + 1));
    }
    
    void update(int a, int b, int l, int r, int v, ll value)
    {
        if (a > r || b < l) return;
        if (a == l && b == r)
        {
            tree[v] = value;
            return;
        }
        push(l, r, v);
        int m = (l + r) >> 1;
        update(a, min(b, m), l, m, v << 1, value);
        update(max(a, m + 1), b, m + 1, r, (v << 1) + 1, value);
        tree[v] = max(tree[v << 1], tree[(v << 1) + 1]);
    }
    
public:
    
    SegmentTree(int n = 0) : amount(n)
    {
        tree.resize(4 * amount + 5, -1);
    }
    
    SegmentTree(vector<ll>& a) : amount((int)a.size())
    {
        tree.resize(4 * amount + 5);
        mod.resize(4 * amount + 5);
    }
    
    ll get(int a, int b)
    {
        return get(a, b, 0, amount - 1, 1);
    }
    
    void update(int a, int b, ll value)
    {
        update(a, b, 0, amount - 1, 1, value);
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<pair<int, int>> ab(n);
    vector<ll> h(n);
    for (int i = 0; i < n; ++i) cin >> h[i] >> ab[i].first >> ab[i].second;
    int q;
    cin >> q;
    vector<pair<int, int>> queries(q);
    for (auto &[l, r] : queries)
    {
        cin >> l >> r;
        --l;
        --r;
    }
    vector<int> inds(q);
    vector<pair<pair<int, int>, int>> events;
    segtree st(n);
    events.reserve(2 * n);
    iota(inds.begin(), inds.end(), 0);
    sort(inds.begin(), inds.end(), [&queries](int a, int b){ return queries[a].second < queries[b].second; });
    for (int i = 0; i < n; ++i)
    {
        events.emplace_back(pair(i + ab[i].first, 0), i);
        events.emplace_back(pair(i + ab[i].second, 1), i);
    }
    sort(events.begin(), events.end());
    SegmentTree st2(n);
    vector<ll> result(q, -1);
    for (int i = 0, indE = 0, indQ = 0; i < n; ++i)
    {
        while (indE < 2 * n && events[indE].first <= pair(i, 0))
        {
            st.updateH(events[indE].second, -h[events[indE].second]);
            ++indE;
        }
        if (i - ab[i].first >= 0) st.updateM(max(0, i - ab[i].second), i - ab[i].first, h[i]);
        while (indQ < q && queries[inds[indQ]].second == i)
        {
            result[inds[indQ]] = max({result[inds[indQ]], st.get(queries[inds[indQ]].first, queries[inds[indQ]].second), st2.get(queries[inds[indQ]].first, queries[inds[indQ]].second)});
            ++indQ;
        }
        while (indE < 2 * n && events[indE].first <= pair(i, 1))
        {
            st2.update(events[indE].second, events[indE].second, st.get(events[indE].second, events[indE].second));
            st.updateH(events[indE].second, -INF);
            ++indE;
        }
        
    }
    reverse(h.begin(), h.end());
    reverse(ab.begin(), ab.end());
    for (auto &i : queries) i = {n - i.second - 1, n - i.first - 1};
    events.clear();
    sort(inds.begin(), inds.end(), [&queries](int a, int b){ return queries[a].second < queries[b].second; });
    for (int i = 0; i < n; ++i)
    {
        events.emplace_back(pair(i + ab[i].first, 0), i);
        events.emplace_back(pair(i + ab[i].second, 1), i);
    }
    sort(events.begin(), events.end());
    st = segtree(n);
    st2 = SegmentTree(n);
    for (int i = 0, indE = 0, indQ = 0; i < n; ++i)
    {
        while (indE < 2 * n && events[indE].first <= pair(i, 0))
        {
            st.updateH(events[indE].second, -h[events[indE].second]);
            ++indE;
        }
        if (i - ab[i].first >= 0) st.updateM(max(0, i - ab[i].second), i - ab[i].first, h[i]);
        while (indQ < q && queries[inds[indQ]].second == i)
        {
            result[inds[indQ]] = max({result[inds[indQ]], st.get(queries[inds[indQ]].first, queries[inds[indQ]].second), st2.get(queries[inds[indQ]].first, queries[inds[indQ]].second)});
            ++indQ;
        }
        while (indE < 2 * n && events[indE].first <= pair(i, 1))
        {
            st2.update(events[indE].second, events[indE].second, st.get(events[indE].second, events[indE].second));
            st.updateH(events[indE].second, -INF);
            ++indE;
        }
        
    }
    for (ll i : result) cout << i << '\n';
    return 0;
}
/*
 5
 10 2 4
 1 1 1
 2 1 3
 1 1
 1
 100 1 1
 5
 1 2
 2 3
 1 3
 1 4
 1 5
 */

/*
 2
 10 2 4
 1 1 1
 1
 1 2
 */
//10 1 2 1 100
/*
3
6 1 1
8 1 1
2 2 2
1
1 3
*/

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 46652 KB Output is correct
2 Correct 602 ms 56424 KB Output is correct
3 Correct 364 ms 39764 KB Output is correct
4 Correct 530 ms 56528 KB Output is correct
5 Correct 208 ms 26104 KB Output is correct
6 Correct 605 ms 56436 KB Output is correct
7 Correct 566 ms 48968 KB Output is correct
8 Correct 608 ms 56424 KB Output is correct
9 Correct 75 ms 9180 KB Output is correct
10 Correct 609 ms 56428 KB Output is correct
11 Correct 327 ms 35404 KB Output is correct
12 Correct 612 ms 56432 KB Output is correct
13 Incorrect 468 ms 56324 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

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