oj.uz

Submission #144386

# Submission time Handle Problem Language Result Execution time Memory
144386 2019-08-16T19:12:30 Z osaaateiasavtnl Two Antennas (JOI19_antennas) C++14
100 / 100
 814 ms 69704 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 2e5 + 7, INF = 1e18 + 7;
int n, q;
struct E { int h, a, b; } a[N];
namespace OP {
int mn[N << 2], mx[N << 2], mn1[N << 2], mx1[N << 2], tans[N << 2];
void rec(int v) { tans[v] = max(mx[v] - mn1[v], mx1[v] - mn[v]); }
int get(int v) { return max(mx[v] - mn1[v], mx1[v] - mn[v]); }
void push(int v) {
    for (int i = v * 2 + 1; i <= v * 2 + 2; ++i) {
        mn[i] = min(mn[i], mn[v]); mx[i] = max(mx[i], mx[v]);
        tans[i] = max(tans[i], get(i));
    }
    mn[v] = INF; mx[v] = -INF;
}
void relax(int v) {
    tans[v] = max(tans[v * 2 + 1], tans[v * 2 + 2]);
    mn1[v] = min(mn1[v * 2 + 1], mn1[v * 2 + 2]);
    mx1[v] = max(mx1[v * 2 + 1], mx1[v * 2 + 2]);
}
void upd(int v, int tl, int tr, int l, int r, int x) {
    if (tr < l || r < tl) return;
    if (l <= tl && tr <= r) { 
        mn[v] = min(mn[v], x); mx[v] = max(mx[v], x); 
        tans[v] = max(tans[v], get(v));
        return; 
    }
    int tm = (tl + tr) >> 1;
    push(v);
    upd(v * 2 + 1, tl, tm, l, r, x); upd(v * 2 + 2, tm + 1, tr, l, r, x);
    relax(v);
}
void open(int v, int tl, int tr, int p) {
    if (tl == tr) { mn[v] = INF; mx[v] = -INF; mn1[v] = mx1[v] = a[p].h; tans[v] = -INF; return; }
    int tm = (tl + tr) >> 1;
    push(v);
    if (p <= tm) open(v * 2 + 1, tl, tm, p); 
    else open(v * 2 + 2, tm + 1, tr, p);
    relax(v);
}
int close(int v, int tl, int tr, int p) {
    if (tl == tr) { int ans = tans[v]; mn[v] = mn1[v] = INF; mx[v] = mx1[v] = -INF; tans[v] = -INF; return ans; }
    int tm = (tl + tr) >> 1;
    push(v);
    int t; 
    if (p <= tm) t = close(v * 2 + 1, tl, tm, p); 
    else t = close(v * 2 + 2, tm + 1, tr, p);
    relax(v); return t;
}   
int get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl) return -INF;
    if (l <= tl && tr <= r) return tans[v];
    int tm = (tl + tr) >> 1;
    push(v);
    return max(get(v * 2 + 1, tl, tm, l, r), get(v * 2 + 2, tm + 1, tr, l, r));
}
};
vector <ii> mem[N];
vector <int> open[N], close[N];
int tree[N << 2];
void add(int v, int tl, int tr, int p, int x) {
    if (tl == tr) { tree[v] = x; return; }
    int tm = (tl + tr) >> 1;
    if (p <= tm) add(v * 2 + 1, tl, tm, p, x);
    else add(v * 2 + 2, tm + 1, tr, p, x);
    tree[v] = max(tree[v * 2 + 1], tree[v * 2 + 2]);
}
int get(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl) return -INF;
    if (l <= tl && tr <= r) return tree[v];
    int tm = (tl + tr) >> 1;
    return max(get(v * 2 + 1, tl, tm, l, r), get(v * 2 + 2, tm + 1, tr, l, r));
}
void open_(int i) { OP::open(0, 0, N, i); }
void close_(int i) { add(0, 0, N, i, OP::close(0, 0, N, i)); }
void add(int i) {
    int l = i - a[i].b, r = i - a[i].a;
    if (r < 0) return;
    l = max(l, 0ll);
    OP::upd(0, 0, N, l, r, a[i].h);
}
int get(int l, int r) { return max(get(0, 0, N, l, r), OP::get(0, 0, N, l, r)); }
int ans[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    for (int i = 0; i < (N << 2); ++i) { OP::mn[i] = OP::mn1[i] = INF; OP::mx[i] = OP::mx1[i] = -INF; OP::tans[i] = -INF; tree[i] = -INF; }
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].h >> a[i].a >> a[i].b; 
        if (i + a[i].a < N) open[i + a[i].a].app(i); 
        if (i + a[i].b + 1 < N) close[i + a[i].b + 1].app(i); 
    }
    cin >> q;
    for (int i = 0; i < q; ++i) { int l, r; cin >> l >> r; mem[r].app({l, i}); }
    for (int i = 1; i <= n; ++i) {
        for (int e : open[i]) open_(e);
        for (int e : close[i]) close_(e);
        add(i);
        for (auto e : mem[i]) ans[e.second] = get(e.first, i);
    }
    for (int i = 0; i < q; ++i) { 
        if (ans[i] < 0) cout << "-1\n";
        else cout << ans[i] << '\n';
    }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 51960 KB Output is correct
2 Correct 50 ms 52092 KB Output is correct
3 Correct 49 ms 52092 KB Output is correct
4 Correct 49 ms 52216 KB Output is correct
5 Correct 48 ms 52052 KB Output is correct
6 Correct 49 ms 52088 KB Output is correct
7 Correct 49 ms 52088 KB Output is correct
8 Correct 57 ms 52088 KB Output is correct
9 Correct 58 ms 52120 KB Output is correct
10 Correct 49 ms 52088 KB Output is correct
11 Correct 49 ms 52088 KB Output is correct
12 Correct 52 ms 52088 KB Output is correct
13 Correct 49 ms 52088 KB Output is correct
14 Correct 50 ms 52088 KB Output is correct
15 Correct 49 ms 52088 KB Output is correct
16 Correct 49 ms 52088 KB Output is correct
17 Correct 50 ms 52056 KB Output is correct
18 Correct 67 ms 52088 KB Output is correct
19 Correct 49 ms 51996 KB Output is correct
20 Correct 53 ms 52060 KB Output is correct
21 Correct 58 ms 52088 KB Output is correct
22 Correct 49 ms 52088 KB Output is correct
23 Correct 57 ms 52088 KB Output is correct
24 Correct 58 ms 52088 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 51960 KB Output is correct
2 Correct 50 ms 52092 KB Output is correct
3 Correct 49 ms 52092 KB Output is correct
4 Correct 49 ms 52216 KB Output is correct
5 Correct 48 ms 52052 KB Output is correct
6 Correct 49 ms 52088 KB Output is correct
7 Correct 49 ms 52088 KB Output is correct
8 Correct 57 ms 52088 KB Output is correct
9 Correct 58 ms 52120 KB Output is correct
10 Correct 49 ms 52088 KB Output is correct
11 Correct 49 ms 52088 KB Output is correct
12 Correct 52 ms 52088 KB Output is correct
13 Correct 49 ms 52088 KB Output is correct
14 Correct 50 ms 52088 KB Output is correct
15 Correct 49 ms 52088 KB Output is correct
16 Correct 49 ms 52088 KB Output is correct
17 Correct 50 ms 52056 KB Output is correct
18 Correct 67 ms 52088 KB Output is correct
19 Correct 49 ms 51996 KB Output is correct
20 Correct 53 ms 52060 KB Output is correct
21 Correct 58 ms 52088 KB Output is correct
22 Correct 49 ms 52088 KB Output is correct
23 Correct 57 ms 52088 KB Output is correct
24 Correct 58 ms 52088 KB Output is correct
25 Correct 191 ms 58436 KB Output is correct
26 Correct 67 ms 52984 KB Output is correct
27 Correct 257 ms 60776 KB Output is correct
28 Correct 268 ms 60892 KB Output is correct
29 Correct 191 ms 58616 KB Output is correct
30 Correct 187 ms 58168 KB Output is correct
31 Correct 225 ms 60024 KB Output is correct
32 Correct 264 ms 60792 KB Output is correct
33 Correct 245 ms 60280 KB Output is correct
34 Correct 149 ms 56568 KB Output is correct
35 Correct 273 ms 60688 KB Output is correct
36 Correct 287 ms 60920 KB Output is correct
37 Correct 163 ms 56824 KB Output is correct
38 Correct 253 ms 59944 KB Output is correct
39 Correct 80 ms 53496 KB Output is correct
40 Correct 252 ms 59768 KB Output is correct
41 Correct 194 ms 57988 KB Output is correct
42 Correct 248 ms 59760 KB Output is correct
43 Correct 128 ms 55160 KB Output is correct
44 Correct 252 ms 59832 KB Output is correct
45 Correct 84 ms 53764 KB Output is correct
46 Correct 248 ms 59896 KB Output is correct
47 Correct 117 ms 54392 KB Output is correct
48 Correct 263 ms 60016 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 60920 KB Output is correct
2 Correct 424 ms 60928 KB Output is correct
3 Correct 304 ms 60732 KB Output is correct
4 Correct 405 ms 60840 KB Output is correct
5 Correct 209 ms 59280 KB Output is correct
6 Correct 387 ms 60900 KB Output is correct
7 Correct 353 ms 61048 KB Output is correct
8 Correct 413 ms 61048 KB Output is correct
9 Correct 95 ms 54904 KB Output is correct
10 Correct 434 ms 61032 KB Output is correct
11 Correct 284 ms 60592 KB Output is correct
12 Correct 402 ms 60984 KB Output is correct
13 Correct 270 ms 59500 KB Output is correct
14 Correct 270 ms 59580 KB Output is correct
15 Correct 251 ms 59504 KB Output is correct
16 Correct 283 ms 59972 KB Output is correct
17 Correct 278 ms 59636 KB Output is correct
18 Correct 272 ms 59960 KB Output is correct
19 Correct 274 ms 59244 KB Output is correct
20 Correct 254 ms 59752 KB Output is correct
21 Correct 239 ms 59236 KB Output is correct
22 Correct 254 ms 59496 KB Output is correct
23 Correct 255 ms 59376 KB Output is correct
24 Correct 275 ms 59504 KB Output is correct

Subtask #4
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 51960 KB Output is correct
2 Correct 50 ms 52092 KB Output is correct
3 Correct 49 ms 52092 KB Output is correct
4 Correct 49 ms 52216 KB Output is correct
5 Correct 48 ms 52052 KB Output is correct
6 Correct 49 ms 52088 KB Output is correct
7 Correct 49 ms 52088 KB Output is correct
8 Correct 57 ms 52088 KB Output is correct
9 Correct 58 ms 52120 KB Output is correct
10 Correct 49 ms 52088 KB Output is correct
11 Correct 49 ms 52088 KB Output is correct
12 Correct 52 ms 52088 KB Output is correct
13 Correct 49 ms 52088 KB Output is correct
14 Correct 50 ms 52088 KB Output is correct
15 Correct 49 ms 52088 KB Output is correct
16 Correct 49 ms 52088 KB Output is correct
17 Correct 50 ms 52056 KB Output is correct
18 Correct 67 ms 52088 KB Output is correct
19 Correct 49 ms 51996 KB Output is correct
20 Correct 53 ms 52060 KB Output is correct
21 Correct 58 ms 52088 KB Output is correct
22 Correct 49 ms 52088 KB Output is correct
23 Correct 57 ms 52088 KB Output is correct
24 Correct 58 ms 52088 KB Output is correct
25 Correct 191 ms 58436 KB Output is correct
26 Correct 67 ms 52984 KB Output is correct
27 Correct 257 ms 60776 KB Output is correct
28 Correct 268 ms 60892 KB Output is correct
29 Correct 191 ms 58616 KB Output is correct
30 Correct 187 ms 58168 KB Output is correct
31 Correct 225 ms 60024 KB Output is correct
32 Correct 264 ms 60792 KB Output is correct
33 Correct 245 ms 60280 KB Output is correct
34 Correct 149 ms 56568 KB Output is correct
35 Correct 273 ms 60688 KB Output is correct
36 Correct 287 ms 60920 KB Output is correct
37 Correct 163 ms 56824 KB Output is correct
38 Correct 253 ms 59944 KB Output is correct
39 Correct 80 ms 53496 KB Output is correct
40 Correct 252 ms 59768 KB Output is correct
41 Correct 194 ms 57988 KB Output is correct
42 Correct 248 ms 59760 KB Output is correct
43 Correct 128 ms 55160 KB Output is correct
44 Correct 252 ms 59832 KB Output is correct
45 Correct 84 ms 53764 KB Output is correct
46 Correct 248 ms 59896 KB Output is correct
47 Correct 117 ms 54392 KB Output is correct
48 Correct 263 ms 60016 KB Output is correct
49 Correct 406 ms 60920 KB Output is correct
50 Correct 424 ms 60928 KB Output is correct
51 Correct 304 ms 60732 KB Output is correct
52 Correct 405 ms 60840 KB Output is correct
53 Correct 209 ms 59280 KB Output is correct
54 Correct 387 ms 60900 KB Output is correct
55 Correct 353 ms 61048 KB Output is correct
56 Correct 413 ms 61048 KB Output is correct
57 Correct 95 ms 54904 KB Output is correct
58 Correct 434 ms 61032 KB Output is correct
59 Correct 284 ms 60592 KB Output is correct
60 Correct 402 ms 60984 KB Output is correct
61 Correct 270 ms 59500 KB Output is correct
62 Correct 270 ms 59580 KB Output is correct
63 Correct 251 ms 59504 KB Output is correct
64 Correct 283 ms 59972 KB Output is correct
65 Correct 278 ms 59636 KB Output is correct
66 Correct 272 ms 59960 KB Output is correct
67 Correct 274 ms 59244 KB Output is correct
68 Correct 254 ms 59752 KB Output is correct
69 Correct 239 ms 59236 KB Output is correct
70 Correct 254 ms 59496 KB Output is correct
71 Correct 255 ms 59376 KB Output is correct
72 Correct 275 ms 59504 KB Output is correct
73 Correct 698 ms 67520 KB Output is correct
74 Correct 455 ms 61816 KB Output is correct
75 Correct 678 ms 69624 KB Output is correct
76 Correct 796 ms 69624 KB Output is correct
77 Correct 451 ms 65528 KB Output is correct
78 Correct 666 ms 66936 KB Output is correct
79 Correct 743 ms 69624 KB Output is correct
80 Correct 814 ms 69704 KB Output is correct
81 Correct 363 ms 62968 KB Output is correct
82 Correct 595 ms 65272 KB Output is correct
83 Correct 693 ms 69136 KB Output is correct
84 Correct 802 ms 69624 KB Output is correct
85 Correct 512 ms 63852 KB Output is correct
86 Correct 710 ms 67080 KB Output is correct
87 Correct 326 ms 60656 KB Output is correct
88 Correct 756 ms 67512 KB Output is correct
89 Correct 580 ms 64752 KB Output is correct
90 Correct 672 ms 67244 KB Output is correct
91 Correct 405 ms 61548 KB Output is correct
92 Correct 693 ms 66668 KB Output is correct
93 Correct 320 ms 60388 KB Output is correct
94 Correct 661 ms 66664 KB Output is correct
95 Correct 380 ms 61040 KB Output is correct
96 Correct 675 ms 66644 KB Output is correct