oj.uz

Submission #938882

# Submission time Handle Problem Language Result Execution time Memory
938882 2024-03-05T18:11:47 Z danikoynov Two Antennas (JOI19_antennas) C++14
13 / 100
 3000 ms 41328 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 int maxn = 2e5 + 10;

struct query
{
    int l, r, idx;

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

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

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

    for (int 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 int inf = 2e9 + 10;
int act[maxn], low[maxn];
vector < int > upd[2][2 * maxn];

void sweep_line()
{
    ///cerr << task[49].l << " : " << task[49].r << endl;
    for (int i = 1; i <= n; i ++)
    {
        low[i] = inf;
        act[i] = 0;
        upd[0][i + a[i]].push_back(i);
        upd[1][i + b[i]].push_back(i);
    }

    for (int i = 1; i <= n; i ++)
    {
        for (int cur : upd[0][i])
        {
            act[cur] = 1;
        }

        int lf = max(1, i - b[i]), rf = max(0, i - a[i]);
        for (int j = lf; j <= rf; j ++)
        {
            if (act[j])
                low[j] = min(low[j], h[i]);
        }

        for (int cur : upd[1][i])
        {
            act[cur] = 0;
        }

        for (query cur : spot[i])
        {
            for (int j = cur.l; j <= cur.r; j ++)
            {
                ans[cur.idx] = max(ans[cur.idx], h[j] - low[j]);
            }
        }
    }
}

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

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

    for (int i = 1; i <= q; i ++)
    {
        int 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 print()
{
    for (int i = 1; i <= q; i ++)
    {

         cout << ans[i]  << endl;

    }
}
void solve()
{
    input();

    sweep_line();
    reverse_data();
    sweep_line();
    print();
}

int main()
{
    speed();
    ///freopen("output.txt", "w", stdout);
        solve();
    return 0;
}
/**
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
68
87 89
81 90
38 95
73 93
69 70
4 98
77 93
73 110
49 54
101 102
107 109
20 63
55 94
61 95
104 107
80 101
73 101
44 51
92 94
75 82
15 83
47 59
32 79
30 62
48 79
18 45
33 86
74 90
107 109
37 87
60 78
1 48
93 99
78 89
38 96
61 107
6 61
110 111
81 92
98 103
76 95
43 107
11 81
56 65
49 102
70 87
84 85
44 109
66 111
110 111
6 59
6 12
8 64
7 42
21 81
70 88
53 104
46 103
8 44
103 106
34 38
72 103
39 45
38 51
80 88
7 79
105 107
17 28

*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30808 KB Output is correct
2 Correct 7 ms 30924 KB Output is correct
3 Correct 7 ms 30948 KB Output is correct
4 Correct 7 ms 30812 KB Output is correct
5 Correct 7 ms 30812 KB Output is correct
6 Correct 7 ms 30812 KB Output is correct
7 Correct 7 ms 30812 KB Output is correct
8 Correct 7 ms 30812 KB Output is correct
9 Correct 7 ms 30812 KB Output is correct
10 Correct 7 ms 30808 KB Output is correct
11 Correct 7 ms 30812 KB Output is correct
12 Correct 7 ms 30944 KB Output is correct
13 Correct 8 ms 30812 KB Output is correct
14 Correct 7 ms 30812 KB Output is correct
15 Correct 7 ms 30812 KB Output is correct
16 Correct 7 ms 30812 KB Output is correct
17 Correct 6 ms 30812 KB Output is correct
18 Correct 7 ms 30812 KB Output is correct
19 Correct 7 ms 30992 KB Output is correct
20 Correct 7 ms 30812 KB Output is correct
21 Correct 7 ms 30812 KB Output is correct
22 Correct 7 ms 30812 KB Output is correct
23 Correct 7 ms 30812 KB Output is correct
24 Correct 7 ms 30812 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30808 KB Output is correct
2 Correct 7 ms 30924 KB Output is correct
3 Correct 7 ms 30948 KB Output is correct
4 Correct 7 ms 30812 KB Output is correct
5 Correct 7 ms 30812 KB Output is correct
6 Correct 7 ms 30812 KB Output is correct
7 Correct 7 ms 30812 KB Output is correct
8 Correct 7 ms 30812 KB Output is correct
9 Correct 7 ms 30812 KB Output is correct
10 Correct 7 ms 30808 KB Output is correct
11 Correct 7 ms 30812 KB Output is correct
12 Correct 7 ms 30944 KB Output is correct
13 Correct 8 ms 30812 KB Output is correct
14 Correct 7 ms 30812 KB Output is correct
15 Correct 7 ms 30812 KB Output is correct
16 Correct 7 ms 30812 KB Output is correct
17 Correct 6 ms 30812 KB Output is correct
18 Correct 7 ms 30812 KB Output is correct
19 Correct 7 ms 30992 KB Output is correct
20 Correct 7 ms 30812 KB Output is correct
21 Correct 7 ms 30812 KB Output is correct
22 Correct 7 ms 30812 KB Output is correct
23 Correct 7 ms 30812 KB Output is correct
24 Correct 7 ms 30812 KB Output is correct
25 Correct 98 ms 36940 KB Output is correct
26 Correct 30 ms 31568 KB Output is correct
27 Correct 215 ms 39532 KB Output is correct
28 Correct 239 ms 39256 KB Output is correct
29 Correct 103 ms 37124 KB Output is correct
30 Correct 161 ms 36904 KB Output is correct
31 Correct 74 ms 38360 KB Output is correct
32 Correct 242 ms 39176 KB Output is correct
33 Correct 156 ms 39248 KB Output is correct
34 Correct 118 ms 34896 KB Output is correct
35 Correct 188 ms 39760 KB Output is correct
36 Correct 238 ms 39364 KB Output is correct
37 Correct 135 ms 35408 KB Output is correct
38 Correct 239 ms 38092 KB Output is correct
39 Correct 38 ms 32044 KB Output is correct
40 Correct 239 ms 38188 KB Output is correct
41 Correct 172 ms 36836 KB Output is correct
42 Correct 230 ms 38280 KB Output is correct
43 Correct 79 ms 33616 KB Output is correct
44 Correct 239 ms 38296 KB Output is correct
45 Correct 50 ms 32340 KB Output is correct
46 Correct 229 ms 38224 KB Output is correct
47 Correct 67 ms 32908 KB Output is correct
48 Correct 228 ms 38268 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3100 ms 41328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30808 KB Output is correct
2 Correct 7 ms 30924 KB Output is correct
3 Correct 7 ms 30948 KB Output is correct
4 Correct 7 ms 30812 KB Output is correct
5 Correct 7 ms 30812 KB Output is correct
6 Correct 7 ms 30812 KB Output is correct
7 Correct 7 ms 30812 KB Output is correct
8 Correct 7 ms 30812 KB Output is correct
9 Correct 7 ms 30812 KB Output is correct
10 Correct 7 ms 30808 KB Output is correct
11 Correct 7 ms 30812 KB Output is correct
12 Correct 7 ms 30944 KB Output is correct
13 Correct 8 ms 30812 KB Output is correct
14 Correct 7 ms 30812 KB Output is correct
15 Correct 7 ms 30812 KB Output is correct
16 Correct 7 ms 30812 KB Output is correct
17 Correct 6 ms 30812 KB Output is correct
18 Correct 7 ms 30812 KB Output is correct
19 Correct 7 ms 30992 KB Output is correct
20 Correct 7 ms 30812 KB Output is correct
21 Correct 7 ms 30812 KB Output is correct
22 Correct 7 ms 30812 KB Output is correct
23 Correct 7 ms 30812 KB Output is correct
24 Correct 7 ms 30812 KB Output is correct
25 Correct 98 ms 36940 KB Output is correct
26 Correct 30 ms 31568 KB Output is correct
27 Correct 215 ms 39532 KB Output is correct
28 Correct 239 ms 39256 KB Output is correct
29 Correct 103 ms 37124 KB Output is correct
30 Correct 161 ms 36904 KB Output is correct
31 Correct 74 ms 38360 KB Output is correct
32 Correct 242 ms 39176 KB Output is correct
33 Correct 156 ms 39248 KB Output is correct
34 Correct 118 ms 34896 KB Output is correct
35 Correct 188 ms 39760 KB Output is correct
36 Correct 238 ms 39364 KB Output is correct
37 Correct 135 ms 35408 KB Output is correct
38 Correct 239 ms 38092 KB Output is correct
39 Correct 38 ms 32044 KB Output is correct
40 Correct 239 ms 38188 KB Output is correct
41 Correct 172 ms 36836 KB Output is correct
42 Correct 230 ms 38280 KB Output is correct
43 Correct 79 ms 33616 KB Output is correct
44 Correct 239 ms 38296 KB Output is correct
45 Correct 50 ms 32340 KB Output is correct
46 Correct 229 ms 38224 KB Output is correct
47 Correct 67 ms 32908 KB Output is correct
48 Correct 228 ms 38268 KB Output is correct
49 Execution timed out 3100 ms 41328 KB Time limit exceeded
50 Halted 0 ms 0 KB -