oj.uz

Submission #628848

# Submission time Handle Problem Language Result Execution time Memory
628848 2022-08-13T18:24:14 Z imeimi2000 Radio Towers (IOI22_towers) C++17
17 / 100
 1511 ms 146868 KB 
#include "towers.h"

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;

const int inf = 1e9 + 5;
struct MaxSeg {
    int seg[1 << 18];
    MaxSeg() {
        fill(seg, seg + (1 << 18), -inf);
    }
    void update(int i, int s, int e, int x, int v) {
        if (s == e) {
            seg[i] = v;
            return;
        }
        int m = (s + e) / 2;
        if (x <= m) update(i + i, s, m, x, v);
        else update(i + i + 1, m + 1, e, x, v);
        seg[i] = max(seg[i + i], seg[i + i + 1]);
    }
    int query(int i, int s, int e, int x, int y) const {
        if (e < x || y < s) return -inf;
        if (x <= s && e <= y) return seg[i];
        int m = (s + e) / 2;
        return max(query(i + i, s, m, x, y), query(i + i + 1, m + 1, e, x, y));
    }
    int find(int i, int s, int e, int x, int v) const {
        if (x < s) return 0;
        if (e <= x && seg[i] <= v) return 0;
        if (s == e) return s;
        int m = (s + e) / 2;
        int r = find(i + i + 1, m + 1, e, x, v);
        if (r) return r;
        return find(i + i, s, m, x, v);
    }
};

struct Pst {
    struct Node {
        int L, R, S;
    };
    int root;
    vector<Node> node;
    vector<int> snapshots;
    Pst() {
        root = 0;
        node.push_back(Node { 0, 0, 0 });
        snapshots.push_back(0);
    }
    int update(int i, int s, int e, int x, int v) {
        int j = node.size();
        node.push_back(node[i]);
        node[j].S += v;
        if (s < e) {
            int m = (s + e) / 2;
            if (x <= m) node[j].L = update(node[j].L, s, m, x, v);
            else node[j].R = update(node[j].R, m + 1, e, x, v);
        }
        return j;
    }
    void update(int x, int v) {
        if (x == 0) return;
        root = update(root, 1, inf, x, v);
    }
    int query(int i, int s, int e, int x, int y) const {
        if (!i || e < x || y < s) return 0;
        if (x <= s && e <= y) return node[i].S;
        int m = (s + e) / 2;
        return query(node[i].L, s, m, x, y) + query(node[i].R, m + 1, e, x, y);
    }
    int query(int t, int x, int y) const {
        return query(snapshots[t], 1, inf, x, y);
    }
    void snapshot() {
        snapshots.push_back(root);
    }
};

int n;
struct Tower {
    MaxSeg min_seg, max_seg;
    int maxD[100005];
    int Lmin[100005];
    int Lpos[100005];
    int Lpar[20][100005];
    int V[100005];
    Pst pst;
    void init(vector<int> H) {
        H.insert(H.begin(), inf);
        for (int i = 1; i <= n; ++i) {
            V[i] = H[i];
            min_seg.update(1, 1, n, i, -H[i]);
            max_seg.update(1, 1, n, i, H[i]);
        }
        vector<int> R = { 0, 1 };
        vector<int> L;
        pst.snapshot();
        Lmin[0] = Lmin[1] = inf;
        for (int i = 2; i <= n; ++i) {
            int poped = 0;
            Lmin[i] = inf;
            while (H[R.back()] < H[i]) {
                Lmin[i] = min(Lmin[i], min(Lmin[R.back()], H[R.back()]));
                if (!L.empty() && L.back() == R.back()) L.pop_back();
                R.pop_back();
                ++poped;
            }
            if (!poped) {
                while (!L.empty()) {
                    int x = L.back();
                    pst.update(maxD[x], -1);
                    if (Lmin[x] < H[i]) {
                        maxD[x] = H[x] - H[i];
                        pst.update(maxD[x], 1);
                        break;
                    }
                    else {
                        maxD[x] = H[x] - Lmin[x];
                        pst.update(maxD[x], 1);
                    }
                    L.pop_back();
                }
            }
            else {
                if (!L.empty()) Lpar[0][i] = L.back();
                L.push_back(i);
            }
            Lpos[i] = L.empty() ? 0 : L.back();
            R.push_back(i);
            pst.snapshot();
        }
        for (int i = 1; i < 20; ++i) {
            for (int j = 1; j <= n; ++j) Lpar[i][j] = Lpar[i - 1][Lpar[i - 1][j]];
        }
    }
    int query(int m, int r, int d) const {
        // printf("m = %d, r = %d\n", m, r);
        if (m == r) return 0;
        int ans = pst.query(r, d, inf) - pst.query(m, d, inf);
        int mn = -min_seg.query(1, 1, n, m + 1, r);
        int x = Lpos[m];
        // printf("ans = %d\n", ans);
        if (!x) return ans;
        if (Lmin[x] + d <= V[x] && mn + d <= V[x]) --ans;
        // printf("ans = %d\n", ans);
        for (int i = 20; i--; ) {
            int p = Lpar[i][x];
            if (!p) continue;
            if (Lmin[p] + d <= V[p] && mn + d <= V[p]);
            else x = p, ans -= 1 << i;
        }
        // printf("ans = %d\n", ans);
        x = Lpos[m];
        for (int i = 20; i--; ) {
            int p = Lpar[i][x];
            int g = Lpar[0][p];
            if (!g) continue;
            if (Lmin[g] + d <= V[g] && Lmin[p] + d <= V[g]);
            else x = p, ans += 1 << i;
        }
        // printf("ans = %d\n", ans);
        return ans;
    }
} L, R;

void init(int N, vector<int> H) {
    n = N;
    L.init(H);
    reverse(H.begin(), H.end());
    R.init(H);
}

int max_towers(int L, int R, int D) {
    ++L;
    ++R;
    int V = ::L.max_seg.query(1, 1, n, L, R);
    int M = ::L.max_seg.find(1, 1, n, R, V - 1);
    return ::L.query(M, R, D) + ::R.query(n + 1 - M, n + 1 - L, D) + (V - D >= -::L.min_seg.query(1, 1, n, L, M - 1) && V - D >= -::L.min_seg.query(1, 1, n, M + 1, R)) + 1;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 662 ms 80820 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5080 KB Output is correct
2 Correct 5 ms 6632 KB Output is correct
3 Correct 6 ms 6648 KB Output is correct
4 Correct 5 ms 6624 KB Output is correct
5 Correct 6 ms 6632 KB Output is correct
6 Correct 6 ms 6632 KB Output is correct
7 Correct 7 ms 6632 KB Output is correct
8 Correct 4 ms 4944 KB Output is correct
9 Correct 3 ms 4916 KB Output is correct
10 Correct 5 ms 6484 KB Output is correct
11 Correct 5 ms 6224 KB Output is correct
12 Correct 2 ms 4560 KB Output is correct
13 Incorrect 5 ms 6856 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
14 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5080 KB Output is correct
2 Correct 5 ms 6632 KB Output is correct
3 Correct 6 ms 6648 KB Output is correct
4 Correct 5 ms 6624 KB Output is correct
5 Correct 6 ms 6632 KB Output is correct
6 Correct 6 ms 6632 KB Output is correct
7 Correct 7 ms 6632 KB Output is correct
8 Correct 4 ms 4944 KB Output is correct
9 Correct 3 ms 4916 KB Output is correct
10 Correct 5 ms 6484 KB Output is correct
11 Correct 5 ms 6224 KB Output is correct
12 Correct 2 ms 4560 KB Output is correct
13 Incorrect 5 ms 6856 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1022 ms 146232 KB 59096th lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 39228 KB Output is correct
2 Correct 1285 ms 146672 KB Output is correct
3 Correct 1150 ms 146756 KB Output is correct
4 Correct 1369 ms 146636 KB Output is correct
5 Correct 1392 ms 146636 KB Output is correct
6 Correct 1453 ms 146644 KB Output is correct
7 Correct 1511 ms 146664 KB Output is correct
8 Correct 1130 ms 24628 KB Output is correct
9 Correct 1010 ms 24360 KB Output is correct
10 Correct 1195 ms 73756 KB Output is correct
11 Correct 1093 ms 106168 KB Output is correct
12 Correct 238 ms 146756 KB Output is correct
13 Correct 241 ms 146680 KB Output is correct
14 Correct 248 ms 146724 KB Output is correct
15 Correct 71 ms 24364 KB Output is correct
16 Correct 130 ms 68684 KB Output is correct
17 Correct 243 ms 143768 KB Output is correct
18 Correct 231 ms 146712 KB Output is correct
19 Correct 224 ms 146692 KB Output is correct
20 Correct 216 ms 146752 KB Output is correct
21 Correct 244 ms 146812 KB Output is correct
22 Correct 219 ms 146868 KB Output is correct
23 Correct 242 ms 146748 KB Output is correct
24 Correct 56 ms 24596 KB Output is correct
25 Correct 65 ms 24388 KB Output is correct
26 Correct 166 ms 116200 KB Output is correct
27 Correct 74 ms 28720 KB Output is correct
28 Correct 8 ms 6660 KB Output is correct
29 Correct 9 ms 6600 KB Output is correct
30 Correct 6 ms 6716 KB Output is correct
31 Correct 4 ms 4944 KB Output is correct
32 Correct 4 ms 5460 KB Output is correct
33 Correct 4 ms 5592 KB Output is correct
34 Correct 8 ms 6636 KB Output is correct
35 Correct 6 ms 6688 KB Output is correct
36 Correct 7 ms 6732 KB Output is correct
37 Correct 6 ms 6664 KB Output is correct
38 Correct 7 ms 6620 KB Output is correct
39 Correct 6 ms 6660 KB Output is correct
40 Correct 5 ms 4992 KB Output is correct
41 Correct 3 ms 4944 KB Output is correct
42 Correct 4 ms 5452 KB Output is correct
43 Correct 6 ms 6088 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5080 KB Output is correct
2 Correct 5 ms 6632 KB Output is correct
3 Correct 6 ms 6648 KB Output is correct
4 Correct 5 ms 6624 KB Output is correct
5 Correct 6 ms 6632 KB Output is correct
6 Correct 6 ms 6632 KB Output is correct
7 Correct 7 ms 6632 KB Output is correct
8 Correct 4 ms 4944 KB Output is correct
9 Correct 3 ms 4916 KB Output is correct
10 Correct 5 ms 6484 KB Output is correct
11 Correct 5 ms 6224 KB Output is correct
12 Correct 2 ms 4560 KB Output is correct
13 Incorrect 5 ms 6856 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 662 ms 80820 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -