oj.uz

Submission #141633

# Submission time Handle Problem Language Result Execution time Memory
141633 2019-08-08T15:04:25 Z HellAngel Two Antennas (JOI19_antennas) C++14
100 / 100
 1158 ms 63644 KB 
#include <bits/stdc++.h>
#define int long long
const int Inf = 1e15;
using namespace std;
const int maxn = 2e5 + 7;
 
int h[maxn], a[maxn], b[maxn], l[maxn], r[maxn], ans[maxn];
int d[4 * maxn], c[maxn], q, n;
vector<int> add[maxn], era[maxn], chk[maxn];
int D[4 * maxn], lz[4 * maxn], C[maxn * 4];
 
void Push_Down(int id, int l, int r)
{
    if(lz[id] != Inf && l < r)
    {
        lz[id * 2] = min(lz[id * 2], lz[id]);
        lz[id * 2 + 1] = min(lz[id * 2 + 1], lz[id]);
        D[id * 2] = max(D[id * 2], C[id * 2] - lz[id * 2]);
        D[id * 2 + 1] = max(D[id * 2 + 1], C[id * 2 + 1] - lz[id * 2 + 1]);
    }
    lz[id] = Inf;
}
 
void Set(int id, int l, int r, int pos, int val)
{
 
    Push_Down(id, l, r);
    if(l == r)
    {
        C[id] = val;
        return;
    }
    Push_Down(id, l, r);
    int mid = l + r >> 1;
    if(pos <= mid) Set(id * 2, l, mid, pos, val);
    else Set(id * 2 + 1, mid + 1, r, pos, val);
    D[id] = max(D[id * 2], D[id * 2 + 1]);
    C[id] = max(C[id * 2], C[id * 2 + 1]);
}
 
void Update(int id, int l, int r, int u, int v, int val)
{
    Push_Down(id, l, r);
    if(l > v || r < u) return;
    if(u <= l && r <= v)
    {
        lz[id] = val;
        D[id] = max(D[id], C[id] - lz[id]);
        return;
    }
    int mid = l + r >> 1;
    Update(id * 2, l, mid, u, v, val);
    Update(id * 2 + 1, mid + 1, r, u, v, val);
    D[id] = max(D[id * 2], D[id * 2 + 1]);
    C[id] = max(C[id * 2], C[id * 2 + 1]);
}
 
int Get(int id, int l, int r, int u, int v)
{
    Push_Down(id, l, r);
    if(l > v || r < u) return -1;
    if(u <= l && r <= v) return D[id];
    int mid = l + r >> 1;
    return max(Get(id * 2, l, mid, u, v), Get(id * 2 + 1, mid + 1, r, u, v));
}
 
void Solve()
{
    for(int i = 0; i < 4 * maxn; i++) lz[i] = Inf, D[i] = C[i] = -Inf;
    for(int i = 1; i <= n + 1; i++) add[i] = era[i] = chk[i] = {};
    for(int i = 1; i <= q; i++) chk[r[i]].push_back(i);
    for(int i = 1; i <= n; i++)
    {
        if(i + a[i] <= n) add[i + a[i]].push_back(i);
        if(i + b[i] + 1 <= n + 1) era[i + b[i] + 1].push_back(i);
    }
    for(int i = 1; i <= n + 1; i++)
    {
        for(auto j: chk[i - 1])
        {
            ans[j] = max(ans[j], Get(1, 1, n, l[j], r[j]));
        }
        if(i == n + 1) return;
        for(auto j: add[i]) Set(1, 1, n, j, h[j]);
        for(auto j: era[i]) Set(1, 1, n, j, -Inf);
        if(i - a[i] >= 1)
        Update(1, 1, n, max(i - b[i], 1ll), i - a[i], h[i]);
    }
}
 
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
    fill_n(ans, maxn, -1);
    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++) cin >> l[i] >> r[i];
    Solve();
    reverse(h + 1, h + n + 1);
    reverse(a + 1, a + n + 1);
    reverse(b + 1, b + n + 1);
    for(int i = 1; i <= q; i++)
    {
        l[i] = n + 1 - l[i];
        r[i] = n + 1 - r[i];
        swap(l[i], r[i]);
    }
    Solve();
    for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

Compilation message

antennas.cpp: In function 'void Set(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
antennas.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:51:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
antennas.cpp: In function 'long long int Get(long long int, long long int, long long int, long long int, long long int)':
antennas.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
antennas.cpp: In function 'int32_t main()':
antennas.cpp:95:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:95:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 34808 KB Output is correct
2 Correct 37 ms 34936 KB Output is correct
3 Correct 37 ms 34808 KB Output is correct
4 Correct 38 ms 34936 KB Output is correct
5 Correct 38 ms 34936 KB Output is correct
6 Correct 37 ms 34936 KB Output is correct
7 Correct 38 ms 35064 KB Output is correct
8 Correct 38 ms 34940 KB Output is correct
9 Correct 37 ms 34808 KB Output is correct
10 Correct 36 ms 34800 KB Output is correct
11 Correct 38 ms 34972 KB Output is correct
12 Correct 38 ms 34808 KB Output is correct
13 Correct 44 ms 34808 KB Output is correct
14 Correct 47 ms 34936 KB Output is correct
15 Correct 39 ms 34888 KB Output is correct
16 Correct 39 ms 34936 KB Output is correct
17 Correct 45 ms 34808 KB Output is correct
18 Correct 37 ms 34808 KB Output is correct
19 Correct 37 ms 34808 KB Output is correct
20 Correct 40 ms 34936 KB Output is correct
21 Correct 38 ms 34936 KB Output is correct
22 Correct 38 ms 34936 KB Output is correct
23 Correct 38 ms 34976 KB Output is correct
24 Correct 38 ms 34936 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 34808 KB Output is correct
2 Correct 37 ms 34936 KB Output is correct
3 Correct 37 ms 34808 KB Output is correct
4 Correct 38 ms 34936 KB Output is correct
5 Correct 38 ms 34936 KB Output is correct
6 Correct 37 ms 34936 KB Output is correct
7 Correct 38 ms 35064 KB Output is correct
8 Correct 38 ms 34940 KB Output is correct
9 Correct 37 ms 34808 KB Output is correct
10 Correct 36 ms 34800 KB Output is correct
11 Correct 38 ms 34972 KB Output is correct
12 Correct 38 ms 34808 KB Output is correct
13 Correct 44 ms 34808 KB Output is correct
14 Correct 47 ms 34936 KB Output is correct
15 Correct 39 ms 34888 KB Output is correct
16 Correct 39 ms 34936 KB Output is correct
17 Correct 45 ms 34808 KB Output is correct
18 Correct 37 ms 34808 KB Output is correct
19 Correct 37 ms 34808 KB Output is correct
20 Correct 40 ms 34936 KB Output is correct
21 Correct 38 ms 34936 KB Output is correct
22 Correct 38 ms 34936 KB Output is correct
23 Correct 38 ms 34976 KB Output is correct
24 Correct 38 ms 34936 KB Output is correct
25 Correct 225 ms 42152 KB Output is correct
26 Correct 68 ms 35832 KB Output is correct
27 Correct 275 ms 44864 KB Output is correct
28 Correct 270 ms 44792 KB Output is correct
29 Correct 190 ms 42188 KB Output is correct
30 Correct 193 ms 41820 KB Output is correct
31 Correct 217 ms 43964 KB Output is correct
32 Correct 269 ms 44700 KB Output is correct
33 Correct 246 ms 44408 KB Output is correct
34 Correct 146 ms 39672 KB Output is correct
35 Correct 268 ms 45072 KB Output is correct
36 Correct 261 ms 44752 KB Output is correct
37 Correct 166 ms 40184 KB Output is correct
38 Correct 287 ms 43840 KB Output is correct
39 Correct 68 ms 36200 KB Output is correct
40 Correct 262 ms 43792 KB Output is correct
41 Correct 202 ms 41716 KB Output is correct
42 Correct 264 ms 43756 KB Output is correct
43 Correct 109 ms 38008 KB Output is correct
44 Correct 261 ms 43764 KB Output is correct
45 Correct 73 ms 36472 KB Output is correct
46 Correct 261 ms 43728 KB Output is correct
47 Correct 93 ms 37240 KB Output is correct
48 Correct 262 ms 43812 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 44172 KB Output is correct
2 Correct 575 ms 45280 KB Output is correct
3 Correct 377 ms 42232 KB Output is correct
4 Correct 576 ms 45332 KB Output is correct
5 Correct 242 ms 39744 KB Output is correct
6 Correct 558 ms 45304 KB Output is correct
7 Correct 497 ms 44060 KB Output is correct
8 Correct 565 ms 45432 KB Output is correct
9 Correct 92 ms 36600 KB Output is correct
10 Correct 564 ms 45436 KB Output is correct
11 Correct 329 ms 41420 KB Output is correct
12 Correct 561 ms 45344 KB Output is correct
13 Correct 355 ms 44780 KB Output is correct
14 Correct 334 ms 44580 KB Output is correct
15 Correct 330 ms 43668 KB Output is correct
16 Correct 304 ms 43864 KB Output is correct
17 Correct 366 ms 45232 KB Output is correct
18 Correct 337 ms 44284 KB Output is correct
19 Correct 346 ms 44208 KB Output is correct
20 Correct 340 ms 44392 KB Output is correct
21 Correct 318 ms 44772 KB Output is correct
22 Correct 340 ms 44392 KB Output is correct
23 Correct 348 ms 44460 KB Output is correct
24 Correct 299 ms 43144 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 34808 KB Output is correct
2 Correct 37 ms 34936 KB Output is correct
3 Correct 37 ms 34808 KB Output is correct
4 Correct 38 ms 34936 KB Output is correct
5 Correct 38 ms 34936 KB Output is correct
6 Correct 37 ms 34936 KB Output is correct
7 Correct 38 ms 35064 KB Output is correct
8 Correct 38 ms 34940 KB Output is correct
9 Correct 37 ms 34808 KB Output is correct
10 Correct 36 ms 34800 KB Output is correct
11 Correct 38 ms 34972 KB Output is correct
12 Correct 38 ms 34808 KB Output is correct
13 Correct 44 ms 34808 KB Output is correct
14 Correct 47 ms 34936 KB Output is correct
15 Correct 39 ms 34888 KB Output is correct
16 Correct 39 ms 34936 KB Output is correct
17 Correct 45 ms 34808 KB Output is correct
18 Correct 37 ms 34808 KB Output is correct
19 Correct 37 ms 34808 KB Output is correct
20 Correct 40 ms 34936 KB Output is correct
21 Correct 38 ms 34936 KB Output is correct
22 Correct 38 ms 34936 KB Output is correct
23 Correct 38 ms 34976 KB Output is correct
24 Correct 38 ms 34936 KB Output is correct
25 Correct 225 ms 42152 KB Output is correct
26 Correct 68 ms 35832 KB Output is correct
27 Correct 275 ms 44864 KB Output is correct
28 Correct 270 ms 44792 KB Output is correct
29 Correct 190 ms 42188 KB Output is correct
30 Correct 193 ms 41820 KB Output is correct
31 Correct 217 ms 43964 KB Output is correct
32 Correct 269 ms 44700 KB Output is correct
33 Correct 246 ms 44408 KB Output is correct
34 Correct 146 ms 39672 KB Output is correct
35 Correct 268 ms 45072 KB Output is correct
36 Correct 261 ms 44752 KB Output is correct
37 Correct 166 ms 40184 KB Output is correct
38 Correct 287 ms 43840 KB Output is correct
39 Correct 68 ms 36200 KB Output is correct
40 Correct 262 ms 43792 KB Output is correct
41 Correct 202 ms 41716 KB Output is correct
42 Correct 264 ms 43756 KB Output is correct
43 Correct 109 ms 38008 KB Output is correct
44 Correct 261 ms 43764 KB Output is correct
45 Correct 73 ms 36472 KB Output is correct
46 Correct 261 ms 43728 KB Output is correct
47 Correct 93 ms 37240 KB Output is correct
48 Correct 262 ms 43812 KB Output is correct
49 Correct 508 ms 44172 KB Output is correct
50 Correct 575 ms 45280 KB Output is correct
51 Correct 377 ms 42232 KB Output is correct
52 Correct 576 ms 45332 KB Output is correct
53 Correct 242 ms 39744 KB Output is correct
54 Correct 558 ms 45304 KB Output is correct
55 Correct 497 ms 44060 KB Output is correct
56 Correct 565 ms 45432 KB Output is correct
57 Correct 92 ms 36600 KB Output is correct
58 Correct 564 ms 45436 KB Output is correct
59 Correct 329 ms 41420 KB Output is correct
60 Correct 561 ms 45344 KB Output is correct
61 Correct 355 ms 44780 KB Output is correct
62 Correct 334 ms 44580 KB Output is correct
63 Correct 330 ms 43668 KB Output is correct
64 Correct 304 ms 43864 KB Output is correct
65 Correct 366 ms 45232 KB Output is correct
66 Correct 337 ms 44284 KB Output is correct
67 Correct 346 ms 44208 KB Output is correct
68 Correct 340 ms 44392 KB Output is correct
69 Correct 318 ms 44772 KB Output is correct
70 Correct 340 ms 44392 KB Output is correct
71 Correct 348 ms 44460 KB Output is correct
72 Correct 299 ms 43144 KB Output is correct
73 Correct 951 ms 58836 KB Output is correct
74 Correct 637 ms 51372 KB Output is correct
75 Correct 898 ms 58104 KB Output is correct
76 Correct 1147 ms 63552 KB Output is correct
77 Correct 597 ms 50808 KB Output is correct
78 Correct 978 ms 59640 KB Output is correct
79 Correct 1050 ms 61136 KB Output is correct
80 Correct 1137 ms 63608 KB Output is correct
81 Correct 435 ms 47740 KB Output is correct
82 Correct 878 ms 57356 KB Output is correct
83 Correct 859 ms 56720 KB Output is correct
84 Correct 1158 ms 63644 KB Output is correct
85 Correct 711 ms 57068 KB Output is correct
86 Correct 936 ms 61532 KB Output is correct
87 Correct 415 ms 50324 KB Output is correct
88 Correct 845 ms 60836 KB Output is correct
89 Correct 876 ms 59328 KB Output is correct
90 Correct 873 ms 61000 KB Output is correct
91 Correct 537 ms 53588 KB Output is correct
92 Correct 890 ms 61276 KB Output is correct
93 Correct 423 ms 51964 KB Output is correct
94 Correct 870 ms 61416 KB Output is correct
95 Correct 492 ms 52856 KB Output is correct
96 Correct 840 ms 60148 KB Output is correct