oj.uz

Submission #1022987

# Submission time Handle Problem Language Result Execution time Memory
1022987 2024-07-14T08:27:22 Z mansur Radio Towers (IOI22_towers) C++17
4 / 100
 4000 ms 20048 KB 
#include "towers.h"
#include<bits/stdc++.h>

using namespace std;

#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second 
#define f first 

using ll = long long;
using pii = pair<int, int>; 
using pll = pair<ll, ll>;

vector<int> h;
int n, k, ok = 1;
const int inf = 1e9, N1 = 3e7;

pii t[N1];

void bld(int u = 1, int tl = 0, int tr = n - 1) {
    if (tl == tr) {
        t[u] = {tl, tl};
        return;
    }
    int m = (tl + tr) / 2;
    bld(u * 2, tl, m);
    bld(u * 2 + 1, m + 1, tr);
    t[u] = t[u * 2 + 1];
    if (h[t[u * 2].f] > h[t[u].f]) t[u].f = t[u * 2].f;
    if (h[t[u * 2].s] < h[t[u].s]) t[u].s = t[u * 2].s;
}

pii get(int l, int r, int u = 1, int tl = 0, int tr = n - 1) {
    if (tl > r || tr < l) return {-1, -1};
    if (tl >= l && tr <= r) return t[u];
    int m = (tl + tr) / 2;
    auto [x1, x2] = get(l, r, u * 2, tl, m);
    auto [y1, y2] = get(l, r, u * 2 + 1, m + 1, tr);
    if (x1 == -1) return {y1, y2};
    if (y1 == -1) return {x1, x2};
    if (h[y1] > h[x1]) x1 = y1;
    if (h[y2] < h[x2]) x2 = y2;
    return {x1, x2};
}

int t2[N1], vl[N1], vr[N1], cur = 1;

void upd(int l, int r, int u = 1, int tl = 1, int tr = inf) {
    if (tl > r || tr < l) return;
    if (tl >= l && tr <= r) {
        t2[u]++;
        return;
    }
    int m = (tl + tr) / 2;
    if (!vl[u]) vl[u] = ++cur;
    if (!vr[u]) vr[u] = ++cur;
    upd(l, r, vl[u], tl, m);
    upd(l, r, vr[u], m + 1, tr);
}

int gt(int p, int u = 1, int tl = 1, int tr = inf) {
    if (tl == tr) return t2[u];
    int m = (tl + tr) / 2;
    if (p <= m) {
        if (vl[u]) return gt(p, vl[u], tl, m) + t2[u];
        return t2[u];
    }
    if (vr[u]) return gt(p, vr[u], m + 1, tr) + t2[u];
    return t2[u];
}

void calc(int l, int r, int mx) {
    if (r < l) return;
    if (l == r) {
        upd(1, mx - h[l]);
        return; 
    }
    auto [pos, ps] = get(l, r);
    if (pos == l) calc(l + 1, r, mx);
    else if (pos == r) calc(l, r - 1, mx);
    else {
        upd(h[pos] - h[ps] + 1, inf);
        calc(l, pos - 1, h[pos]);
        calc(pos + 1, r, h[pos]);
    }
}

void init(int N, vector<int> H) {
    n = N, h = H;
    k = n - 1;
    for (int i = 1; i < n; i++) {
        if (h[i] < h[i - 1]) {
            k = i - 1;
            break;
        }
    }
    for (int i = 1; i < k; i++) {
        if (h[i - 1] > h[i]) ok = 0;
    }
    for (int i = k + 1; i < n; i++) {
        if (h[i - 1] < h[i]) ok = 0;
    }
    bld();
    calc(0, n - 1, inf);
}

int f(int l, int r, int d, int mx) {
    if (r < l) return 0;
    if (l == r) return (h[l] <= mx);
    auto [pos, ps] = get(l, r);
    if (h[ps] > mx) return 0;
    if (pos == l) return f(l + 1, r, d, mx);
    if (pos == r) return f(l, r - 1, d, mx);
    return max(1, f(l, pos - 1, d, min(mx, h[pos] - d)) + f(pos + 1, r, d, min(mx, h[pos] - d)));
}

int max_towers(int l, int r, int d) {
    if (ok) {
        if (k == -1) return 1;
        if (k <= l || r <= k) return 1;
        if (h[l] > h[k] - d || h[r] > h[k] - d) return 1;
        return 2;
    }
    if (l == 0 && r == n - 1) {
        return gt(d);
    }
    return f(l, r, d, inf);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 2136 KB Output is correct
2 Correct 672 ms 3672 KB Output is correct
3 Correct 640 ms 3656 KB Output is correct
4 Correct 613 ms 3672 KB Output is correct
5 Correct 642 ms 3672 KB Output is correct
6 Correct 643 ms 3672 KB Output is correct
7 Correct 606 ms 3672 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 788 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 1112 KB Output is correct
5 Correct 2 ms 1112 KB Output is correct
6 Correct 1 ms 1112 KB Output is correct
7 Correct 2 ms 1112 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 2 ms 1112 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 856 KB Output is correct
21 Correct 1 ms 1112 KB Output is correct
22 Correct 1 ms 1108 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Incorrect 1 ms 600 KB 1st lines differ - on the 1st token, expected: '34', found: '228'
26 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 788 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 1112 KB Output is correct
5 Correct 2 ms 1112 KB Output is correct
6 Correct 1 ms 1112 KB Output is correct
7 Correct 2 ms 1112 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 2 ms 1112 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 856 KB Output is correct
21 Correct 1 ms 1112 KB Output is correct
22 Correct 1 ms 1108 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Incorrect 1 ms 600 KB 1st lines differ - on the 1st token, expected: '34', found: '228'
26 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 788 KB Output is correct
3 Correct 1 ms 856 KB Output is correct
4 Correct 1 ms 1112 KB Output is correct
5 Correct 2 ms 1112 KB Output is correct
6 Correct 1 ms 1112 KB Output is correct
7 Correct 2 ms 1112 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 2 ms 1112 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 856 KB Output is correct
21 Correct 1 ms 1112 KB Output is correct
22 Correct 1 ms 1108 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Incorrect 1 ms 600 KB 1st lines differ - on the 1st token, expected: '34', found: '228'
26 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 2136 KB Output is correct
2 Correct 672 ms 3672 KB Output is correct
3 Correct 640 ms 3656 KB Output is correct
4 Correct 613 ms 3672 KB Output is correct
5 Correct 642 ms 3672 KB Output is correct
6 Correct 643 ms 3672 KB Output is correct
7 Correct 606 ms 3672 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 788 KB Output is correct
13 Correct 1 ms 856 KB Output is correct
14 Correct 1 ms 1112 KB Output is correct
15 Correct 2 ms 1112 KB Output is correct
16 Correct 1 ms 1112 KB Output is correct
17 Correct 2 ms 1112 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 856 KB Output is correct
26 Correct 1 ms 1112 KB Output is correct
27 Correct 2 ms 1112 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 856 KB Output is correct
31 Correct 1 ms 1112 KB Output is correct
32 Correct 1 ms 1108 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Incorrect 1 ms 600 KB 1st lines differ - on the 1st token, expected: '34', found: '228'
36 Halted 0 ms 0 KB -