oj.uz

Submission #1022896

# Submission time Handle Problem Language Result Execution time Memory
1022896 2024-07-14T07:15:21 Z mansur Radio Towers (IOI22_towers) C++17
4 / 100
 4000 ms 3672 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 = 2e5;

pii t[4 * 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;
}

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();
}


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 || h[y1] > h[x1]) x1 = y1;
    if (x2 == -1 || h[y2] > h[x2]) x2 = y2;
    return {x1, x2};
}

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;
    }
    return f(l, r, d, inf);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 3160 KB Output is correct
2 Correct 629 ms 3672 KB Output is correct
3 Correct 694 ms 3672 KB Output is correct
4 Correct 653 ms 3672 KB Output is correct
5 Correct 621 ms 3672 KB Output is correct
6 Correct 555 ms 3664 KB Output is correct
7 Correct 565 ms 3672 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 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 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '11'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

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

Subtask #6
0 / 19.0

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

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 3160 KB Output is correct
2 Correct 629 ms 3672 KB Output is correct
3 Correct 694 ms 3672 KB Output is correct
4 Correct 653 ms 3672 KB Output is correct
5 Correct 621 ms 3672 KB Output is correct
6 Correct 555 ms 3664 KB Output is correct
7 Correct 565 ms 3672 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 1 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '11'
12 Halted 0 ms 0 KB -