oj.uz

답안 #938902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938902 2024-03-05T19:25:37 Z danikoynov Two Antennas (JOI19_antennas) C++14
100 / 100
 1220 ms 113276 KB 
#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const ll maxn = 2e5 + 10;

struct query
{
    ll l, r, idx;

    query(ll _l = 0, ll _r = 0, ll _idx = 0)
    {
        l = _l;
        r = _r;
        idx = _idx;
    }
} task[maxn];

ll n, q;
ll h[maxn], a[maxn], b[maxn];
vector < query > spot[maxn];
ll ans[maxn];

void input()
{
    cin >> n;
    for (ll i = 1; i <= n; i ++)
    {
        cin >> h[i] >> a[i] >> b[i];
    }
    cin >> q;
    for (ll i = 1; i <= q; i ++)
        ans[i] = -1;

    for (ll i = 1; i <= q; i ++)
    {
        cin >> task[i].l >> task[i].r;
        task[i].idx = i;
        spot[task[i].r].push_back(task[i]);
    }
}

const ll inf = 2e9 + 10;
ll act[maxn], low[maxn];
vector < ll > upd[2][2 * maxn];

struct node
{
    ll max_dif, max_low, sec_low;
    ll res;

    node()
    {
        max_dif = -inf;
        max_low = inf;
        sec_low = -inf;
        res = -inf;
    }
};

node merge_nodes(node lf, node rf)
{
    /// careful for free node

    node mf;
    mf.max_low = max(lf.max_low, rf.max_low);
    if (lf.max_low != mf.max_low && lf.max_low > mf.sec_low)
        mf.sec_low = lf.max_low;
    if (lf.sec_low != mf.max_low && lf.sec_low > mf.sec_low)
        mf.sec_low = lf.sec_low;

    if (rf.max_low != mf.max_low && rf.max_low > mf.sec_low)
        mf.sec_low = rf.max_low;
    if (rf.sec_low != mf.max_low && rf.sec_low > mf.sec_low)
        mf.sec_low = rf.sec_low;

    if (lf.max_low == mf.max_low && lf.max_dif > mf.max_dif)
        mf.max_dif = lf.max_dif;
    if (rf.max_low == mf.max_low && rf.max_dif > mf.max_dif)
        mf.max_dif = rf.max_dif;

    mf.res = max(lf.res, rf.res);

    return mf;
}

node tree[4 * maxn];

ll lazy[4 * maxn];
ll tag[4 * maxn];
void build(ll root, ll left, ll right)
{
    lazy[root] = tag[root] = 0;
    if (left == right)
    {
        tree[root] = node();
        tree[root].max_dif = 0 - inf;
        tree[root].max_low = inf;
        tree[root].sec_low = -inf;
        tree[root].res = tree[root].max_dif;
        return;
    }

    ll mid = (left + right) / 2;
    build(root * 2, left, mid);
    build(root * 2 + 1, mid + 1, right);

    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}


void push_lazy(ll root, ll left, ll right)
{
    if (tag[root] == 0 || lazy[root] > tree[root].max_low)
    {
        tag[root] = 0;
        lazy[root] = 0;
        return;
    }
    ///cout << "push " << root << " " << left << " " << right << " " << lazy[root] << endl;
        //cout << "push_lazy " << endl;

    ll delta = tree[root].max_low - lazy[root];
    tree[root].max_dif += delta;
    tree[root].res = max(tree[root].res, tree[root].max_dif);
    tree[root].max_low = lazy[root];

    if (left != right)
    {
        lazy[root * 2] = lazy[root];
        lazy[root * 2 + 1] = lazy[root];

        tag[root * 2] = tag[root * 2 + 1] = 1;
    }
    tag[root] = 0;
    lazy[root] = 0;
}

void chmin(ll root, ll left, ll right, ll qleft, ll qright, ll val)
{
    //cout << root << " " << tag[16] << endl;
    push_lazy(root, left, right);
    if (left > qright || right < qleft || tree[root].max_low < val)
        return;

    if (left >= qleft && right <= qright && tree[root].sec_low < val)
    {
        //if (left <= 5 && right >= 5)
        //cout << "CHMIN " << left << " " << right << " " << val << endl;
        lazy[root] = val;
        tag[root] = 1;
        push_lazy(root, left, right);
        return;
    }

    ll mid = (left + right) / 2;
    chmin(root * 2, left, mid, qleft, qright, val);
    chmin(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}

void point_update(ll root, ll left, ll right, ll pivot, ll val)
{
    assert( left <= right);
    push_lazy(root, left, right);

    if (left == right)
    {
        tree[root] = node();
            tree[root].max_dif = val - inf;
        tree[root].max_low = inf;
        tree[root].sec_low = -inf;
        tree[root].res = tree[root].max_dif;
        return;
    }

    ll mid = (left + right) / 2;
    if (pivot <= mid)
    {

        push_lazy(root * 2 + 1, mid + 1, right);
        point_update(root * 2, left, mid, pivot, val);
    }
    else
    {
        push_lazy(root * 2, left, mid);
        point_update(root * 2 + 1, mid + 1, right, pivot, val);
    }

    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}

ll point_query(ll root, ll left, ll right, ll pivot)
{

    push_lazy(root, left, right);
    if (left == right)
        return tree[root].res;
    ll mid = (left + right) / 2;
    if (pivot <= mid)
        return point_query(root * 2, left, mid, pivot);
    else
        return point_query(root * 2 + 1, mid + 1, right, pivot);
}

ll range_query(ll root, ll left, ll right, ll qleft, ll qright)
{

    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return -inf;

    if (left >= qleft && right <= qright)
        return tree[root].res;

    ll mid = (left + right) / 2;
    return max(range_query(root * 2, left, mid, qleft, qright),
               range_query(root * 2 + 1, mid + 1, right, qleft, qright));
}

ll values[maxn];
ll temp[4 * maxn];
void update(int root, int left, int right, int pivot, ll val)
{
    if (left == right)
    {
        temp[root] = val;
        return;
    }

    int mid = (left + right) / 2;
    if (pivot <= mid)
        update(root * 2, left, mid, pivot, val);
        else
            update(root * 2 + 1, mid + 1, right, pivot, val);

        temp[root] = max(temp[root * 2], temp[root * 2 + 1]);
}

void temp_build(int root, int left, int right)
{
    if (left == right)
    {
        temp[root] = -inf;
        return;
    }

    int mid = (left + right) / 2;
    temp_build(root * 2, left, mid);

    temp_build(root * 2 + 1, mid + 1, right);
        temp[root] = max(temp[root * 2], temp[root * 2 + 1]);
}

ll temp_query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return -inf;

    if (left >= qleft && right <= qright)
        return temp[root];

    int mid = (left + right) / 2;
    return max(temp_query(root * 2, left, mid, qleft, qright),
               temp_query(root * 2 + 1, mid + 1, right, qleft, qright));
}
void sweep_line()
{
    ///cerr << task[49].l << " : " << task[49].r << endl;
    for (ll i = 1; i <= n; i ++)
    {
        low[i] = inf;
        act[i] = 0;
        values[i] = -inf;
        upd[0][i + a[i]].push_back(i);
        upd[1][i + b[i]].push_back(i);
    }

    temp_build(1, 1, n);
    build(1, 1, n);
    for (ll i = 1; i <= n; i ++)
    {
        for (ll cur : upd[0][i])
        {
            //cout << "Activate " << cur << endl;
            act[cur] = 1;
            point_update(1, 1, n, cur, h[cur]);
        }

        ll lf = max((ll)1, i - b[i]), rf = max((ll)0, i - a[i]);
        chmin(1, 1, n, lf, rf, h[i]);


        //if (i == 95)
        /**for (int i = 1; i <= n; i ++)
            cerr << act[i] << " ";
        cerr << endl;
        for (int i = 1; i <= n; i ++)
            cerr << low[i] << " ";
        cerr << endl;*/
    //cout << "step " << i << " " << lf << " " << rf << " " << h[i] << endl;
        /**for (int j = 5; j <= 5; j ++)
        {
            ll t1 = point_query(1, 1, n, j);
            if (t1 > h[j] - low[j] && h[j] - low[j] >= 0)
            {
                cout << "STOP!" << endl;
                cout << t1 << " " << h[j] - low[j] << " " << j <<  " " << act[j] << endl;
                exit(0);
            }
        }*/
//            cerr << point_query(1 ,1 ,n, j) << " " << h[j] - low[j] << endl;
  //      cerr << endl;cerr<< "--------------" << endl;}
        for (ll cur : upd[1][i])
        {
            act[cur] = 0;
            //cout << "Deactivate " << cur << endl;

            update(1, 1, n, cur, point_query(1 ,1, n, cur));
            point_update(1, 1, n, cur, 0);
        }

        for (query cur : spot[i])
        {
            ans[cur.idx] = max(ans[cur.idx], temp_query(1, 1, n, cur.l, cur.r));
            /**for (ll j = cur.l; j <= cur.r; j ++)
            {
                ans[cur.idx] = max(ans[cur.idx], values[j]);
            }*/
            ll cs = range_query(1, 1, n, cur.l, cur.r);
            /**if (cs == 841326895)
            {

                cout << "CHANGE HERE" << " " << i << endl;
            }*/
            ans[cur.idx] = max(ans[cur.idx], cs);
        }

    }

    ///cout << "FINISH" << endl;
}

void reverse_data()
{
    reverse(h + 1, h + n + 1);
    reverse(a + 1, a + n + 1);
    reverse(b + 1, b + n + 1);

    for (ll i = 1; i <= n; i ++)
    {
        spot[i].clear();
        upd[0][i].clear();
        upd[1][i].clear();
    }

    for (ll i = 1; i <= q; i ++)
    {
        ll nl = n - task[i].r + 1, nr = n - task[i].l + 1;
        ///cout << i << " : " << nl << " " << nr << endl;
        task[i].l = nl;
        task[i].r = nr;
        spot[task[i].r].push_back(task[i]);
    }
}

void prll()
{
    for (ll i = 1; i <= q; i ++)
    {

        cout << ans[i]  << endl;

    }
}
void solve()
{
    input();

    sweep_line();
    reverse_data();
    sweep_line();
    prll();
}

int main()
{
    speed();
    ///freopen("output.txt", "w", stdout);
    ///freopen("input.txt", "r", stdin);
    solve();
    return 0;
}
/**
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
1
1 2


111
2342163 25 76
738276997 50 52
1669890 26 40
14902411 56 81
899007094 32 85
422634516 2 71
936109680 79 100
638713463 109 110
119468142 28 104\
713258492 104 107
267306336 1 39
973810399 87 90
835929417 43 86
335127775 12 104
840490095 39 66
459253103 11 104
706538155 4 101
194912428 82 96
949222000 73 96
910118043 85 95
226986709 46 100
827920993 75 83
768390729 46 87
314695927 26 30
230872586 49 82
995156805 60 93
497044719 3 103
827805975 75 83
499889872 95 110
590726845 66 73
607078123 59 99
370425117 26 76
490217622 18 32
431150446 77 89
9267221 13 81
693001694 64 95
866349101 26 93
844742196 6 63
655634427 33 88
829473857 67 92
311419714 15 56
900123935 42 87
665050273 42 59
792230034 12 34
847490718 11 21
177697704 66 81
198679758 24 54
668213379 14 45
45659509 82 91
327099919 21 82
118001173 81 85
738608951 80 101
214209461 38 97
324473845 107 109
879267283 109 109
190386778 43 77
881527758 25 44
18672166 13 21
733749641 73 92
653264399 103 110
870234612 104 106
101340654 33 40
710067113 71 104
616465791 8 14
610725519 6 58
376168562 89 109
93289534 79 107
973278654 55 85
183001646 37 50
70495079 47 89
383449644 76 77
239592436 26 49
561740304 21 27
326305893 94 101
376448990 28 85
558483855 107 110
58797040 8 97
479096372 76 90
435216279 42 87
583841698 92 106
277031377 63 110
56594141 34 38
381128173 40 95
275114013 110 110
716940824 48 85
805968236 44 55
997032121 87 92
958531100 90 104
459788004 39 85
618435405 34 97
833464071 87 99
527989265 92 92
708140049 65 87
707609457 2 78
937680650 71 105
969561745 81 102
960172678 49 65
56883909 7 40
602118268 53 69
980631740 95 101
795277058 19 26
572270576 13 89
440358047 25 79
467566899 16 24
634175510 30 38
673050101 21 60
768461341 54 107
331110483 58 87
218341925 68 77
419836470 30 77
925521790 29 36
1
38 95

*/

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 66652 KB Output is correct
2 Correct 12 ms 64856 KB Output is correct
3 Correct 12 ms 64860 KB Output is correct
4 Correct 12 ms 64720 KB Output is correct
5 Correct 13 ms 64856 KB Output is correct
6 Correct 12 ms 66908 KB Output is correct
7 Correct 12 ms 64860 KB Output is correct
8 Correct 12 ms 66908 KB Output is correct
9 Correct 12 ms 64604 KB Output is correct
10 Correct 11 ms 64860 KB Output is correct
11 Correct 11 ms 64656 KB Output is correct
12 Correct 12 ms 64860 KB Output is correct
13 Correct 11 ms 64856 KB Output is correct
14 Correct 11 ms 64860 KB Output is correct
15 Correct 11 ms 64860 KB Output is correct
16 Correct 11 ms 64728 KB Output is correct
17 Correct 12 ms 66908 KB Output is correct
18 Correct 11 ms 66908 KB Output is correct
19 Correct 11 ms 66764 KB Output is correct
20 Correct 13 ms 64732 KB Output is correct
21 Correct 11 ms 64860 KB Output is correct
22 Correct 11 ms 64860 KB Output is correct
23 Correct 12 ms 66784 KB Output is correct
24 Correct 12 ms 66908 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 66652 KB Output is correct
2 Correct 12 ms 64856 KB Output is correct
3 Correct 12 ms 64860 KB Output is correct
4 Correct 12 ms 64720 KB Output is correct
5 Correct 13 ms 64856 KB Output is correct
6 Correct 12 ms 66908 KB Output is correct
7 Correct 12 ms 64860 KB Output is correct
8 Correct 12 ms 66908 KB Output is correct
9 Correct 12 ms 64604 KB Output is correct
10 Correct 11 ms 64860 KB Output is correct
11 Correct 11 ms 64656 KB Output is correct
12 Correct 12 ms 64860 KB Output is correct
13 Correct 11 ms 64856 KB Output is correct
14 Correct 11 ms 64860 KB Output is correct
15 Correct 11 ms 64860 KB Output is correct
16 Correct 11 ms 64728 KB Output is correct
17 Correct 12 ms 66908 KB Output is correct
18 Correct 11 ms 66908 KB Output is correct
19 Correct 11 ms 66764 KB Output is correct
20 Correct 13 ms 64732 KB Output is correct
21 Correct 11 ms 64860 KB Output is correct
22 Correct 11 ms 64860 KB Output is correct
23 Correct 12 ms 66784 KB Output is correct
24 Correct 12 ms 66908 KB Output is correct
25 Correct 132 ms 75092 KB Output is correct
26 Correct 30 ms 65876 KB Output is correct
27 Correct 192 ms 76116 KB Output is correct
28 Correct 210 ms 77840 KB Output is correct
29 Correct 136 ms 73616 KB Output is correct
30 Correct 138 ms 73040 KB Output is correct
31 Correct 165 ms 76956 KB Output is correct
32 Correct 206 ms 75692 KB Output is correct
33 Correct 192 ms 78240 KB Output is correct
34 Correct 109 ms 72276 KB Output is correct
35 Correct 190 ms 77136 KB Output is correct
36 Correct 200 ms 75800 KB Output is correct
37 Correct 122 ms 70924 KB Output is correct
38 Correct 195 ms 76880 KB Output is correct
39 Correct 40 ms 68444 KB Output is correct
40 Correct 204 ms 76932 KB Output is correct
41 Correct 147 ms 75168 KB Output is correct
42 Correct 195 ms 76644 KB Output is correct
43 Correct 74 ms 68432 KB Output is correct
44 Correct 201 ms 74836 KB Output is correct
45 Correct 45 ms 66744 KB Output is correct
46 Correct 204 ms 76948 KB Output is correct
47 Correct 61 ms 69712 KB Output is correct
48 Correct 198 ms 74836 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 555 ms 92348 KB Output is correct
2 Correct 642 ms 98640 KB Output is correct
3 Correct 403 ms 92012 KB Output is correct
4 Correct 640 ms 98168 KB Output is correct
5 Correct 255 ms 80468 KB Output is correct
6 Correct 614 ms 98408 KB Output is correct
7 Correct 548 ms 95664 KB Output is correct
8 Correct 614 ms 98640 KB Output is correct
9 Correct 75 ms 69456 KB Output is correct
10 Correct 636 ms 100596 KB Output is correct
11 Correct 394 ms 86296 KB Output is correct
12 Correct 635 ms 98216 KB Output is correct
13 Correct 381 ms 95060 KB Output is correct
14 Correct 397 ms 96364 KB Output is correct
15 Correct 356 ms 96584 KB Output is correct
16 Correct 345 ms 96788 KB Output is correct
17 Correct 394 ms 95056 KB Output is correct
18 Correct 365 ms 94032 KB Output is correct
19 Correct 366 ms 96628 KB Output is correct
20 Correct 357 ms 94668 KB Output is correct
21 Correct 365 ms 95344 KB Output is correct
22 Correct 376 ms 94560 KB Output is correct
23 Correct 383 ms 94552 KB Output is correct
24 Correct 336 ms 95932 KB Output is correct

Subtask #4
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 66652 KB Output is correct
2 Correct 12 ms 64856 KB Output is correct
3 Correct 12 ms 64860 KB Output is correct
4 Correct 12 ms 64720 KB Output is correct
5 Correct 13 ms 64856 KB Output is correct
6 Correct 12 ms 66908 KB Output is correct
7 Correct 12 ms 64860 KB Output is correct
8 Correct 12 ms 66908 KB Output is correct
9 Correct 12 ms 64604 KB Output is correct
10 Correct 11 ms 64860 KB Output is correct
11 Correct 11 ms 64656 KB Output is correct
12 Correct 12 ms 64860 KB Output is correct
13 Correct 11 ms 64856 KB Output is correct
14 Correct 11 ms 64860 KB Output is correct
15 Correct 11 ms 64860 KB Output is correct
16 Correct 11 ms 64728 KB Output is correct
17 Correct 12 ms 66908 KB Output is correct
18 Correct 11 ms 66908 KB Output is correct
19 Correct 11 ms 66764 KB Output is correct
20 Correct 13 ms 64732 KB Output is correct
21 Correct 11 ms 64860 KB Output is correct
22 Correct 11 ms 64860 KB Output is correct
23 Correct 12 ms 66784 KB Output is correct
24 Correct 12 ms 66908 KB Output is correct
25 Correct 132 ms 75092 KB Output is correct
26 Correct 30 ms 65876 KB Output is correct
27 Correct 192 ms 76116 KB Output is correct
28 Correct 210 ms 77840 KB Output is correct
29 Correct 136 ms 73616 KB Output is correct
30 Correct 138 ms 73040 KB Output is correct
31 Correct 165 ms 76956 KB Output is correct
32 Correct 206 ms 75692 KB Output is correct
33 Correct 192 ms 78240 KB Output is correct
34 Correct 109 ms 72276 KB Output is correct
35 Correct 190 ms 77136 KB Output is correct
36 Correct 200 ms 75800 KB Output is correct
37 Correct 122 ms 70924 KB Output is correct
38 Correct 195 ms 76880 KB Output is correct
39 Correct 40 ms 68444 KB Output is correct
40 Correct 204 ms 76932 KB Output is correct
41 Correct 147 ms 75168 KB Output is correct
42 Correct 195 ms 76644 KB Output is correct
43 Correct 74 ms 68432 KB Output is correct
44 Correct 201 ms 74836 KB Output is correct
45 Correct 45 ms 66744 KB Output is correct
46 Correct 204 ms 76948 KB Output is correct
47 Correct 61 ms 69712 KB Output is correct
48 Correct 198 ms 74836 KB Output is correct
49 Correct 555 ms 92348 KB Output is correct
50 Correct 642 ms 98640 KB Output is correct
51 Correct 403 ms 92012 KB Output is correct
52 Correct 640 ms 98168 KB Output is correct
53 Correct 255 ms 80468 KB Output is correct
54 Correct 614 ms 98408 KB Output is correct
55 Correct 548 ms 95664 KB Output is correct
56 Correct 614 ms 98640 KB Output is correct
57 Correct 75 ms 69456 KB Output is correct
58 Correct 636 ms 100596 KB Output is correct
59 Correct 394 ms 86296 KB Output is correct
60 Correct 635 ms 98216 KB Output is correct
61 Correct 381 ms 95060 KB Output is correct
62 Correct 397 ms 96364 KB Output is correct
63 Correct 356 ms 96584 KB Output is correct
64 Correct 345 ms 96788 KB Output is correct
65 Correct 394 ms 95056 KB Output is correct
66 Correct 365 ms 94032 KB Output is correct
67 Correct 366 ms 96628 KB Output is correct
68 Correct 357 ms 94668 KB Output is correct
69 Correct 365 ms 95344 KB Output is correct
70 Correct 376 ms 94560 KB Output is correct
71 Correct 383 ms 94552 KB Output is correct
72 Correct 336 ms 95932 KB Output is correct
73 Correct 1000 ms 107436 KB Output is correct
74 Correct 681 ms 99492 KB Output is correct
75 Correct 904 ms 106640 KB Output is correct
76 Correct 1152 ms 113276 KB Output is correct
77 Correct 605 ms 93128 KB Output is correct
78 Correct 999 ms 108672 KB Output is correct
79 Correct 1096 ms 110460 KB Output is correct
80 Correct 1131 ms 113244 KB Output is correct
81 Correct 415 ms 83028 KB Output is correct
82 Correct 951 ms 105796 KB Output is correct
83 Correct 795 ms 98668 KB Output is correct
84 Correct 1220 ms 113236 KB Output is correct
85 Correct 736 ms 103128 KB Output is correct
86 Correct 914 ms 108188 KB Output is correct
87 Correct 452 ms 96556 KB Output is correct
88 Correct 962 ms 108668 KB Output is correct
89 Correct 789 ms 105248 KB Output is correct
90 Correct 903 ms 108080 KB Output is correct
91 Correct 608 ms 99384 KB Output is correct
92 Correct 837 ms 110580 KB Output is correct
93 Correct 449 ms 99904 KB Output is correct
94 Correct 814 ms 110568 KB Output is correct
95 Correct 491 ms 100304 KB Output is correct
96 Correct 786 ms 107780 KB Output is correct