oj.uz

Submission #570217

# Submission time Handle Problem Language Result Execution time Memory
570217 2022-05-28T20:45:10 Z timreizin Two Antennas (JOI19_antennas) C++17
22 / 100
 508 ms 50256 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;
            mod[v] = 0;
            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], 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], 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);
    }
    
};

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());
    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));
            ++indQ;
        }
        while (indE < 2 * n && events[indE].first <= pair(i, 1))
        {
            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);
    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));
            ++indQ;
        }
        while (indE < 2 * n && events[indE].first <= pair(i, 1))
        {
            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

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

Subtask #2
0 / 11.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 41016 KB Output is correct
2 Correct 492 ms 45680 KB Output is correct
3 Correct 324 ms 32124 KB Output is correct
4 Correct 485 ms 45700 KB Output is correct
5 Correct 189 ms 21324 KB Output is correct
6 Correct 457 ms 45624 KB Output is correct
7 Correct 430 ms 39644 KB Output is correct
8 Correct 508 ms 45716 KB Output is correct
9 Correct 56 ms 7500 KB Output is correct
10 Correct 470 ms 45620 KB Output is correct
11 Correct 284 ms 28644 KB Output is correct
12 Correct 474 ms 45700 KB Output is correct
13 Correct 364 ms 45644 KB Output is correct
14 Correct 341 ms 50160 KB Output is correct
15 Correct 344 ms 50256 KB Output is correct
16 Correct 295 ms 50056 KB Output is correct
17 Correct 354 ms 50044 KB Output is correct
18 Correct 321 ms 50064 KB Output is correct
19 Correct 336 ms 50076 KB Output is correct
20 Correct 312 ms 50040 KB Output is correct
21 Correct 311 ms 50028 KB Output is correct
22 Correct 322 ms 50060 KB Output is correct
23 Correct 341 ms 50056 KB Output is correct
24 Correct 292 ms 50064 KB Output is correct

Subtask #4
0 / 65.0

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