oj.uz

Submission #771442

# Submission time Handle Problem Language Result Execution time Memory
771442 2023-07-03T02:41:07 Z PurpleCrayon Radio Towers (IOI22_towers) C++17
4 / 100
 4000 ms 13252 KB 
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;
const int L = 20;

int n, a[N], st[N][L];
vector<pair<int, int>> store;
vector<int> base;
vector<int> ord;

void build_rmq() {
    for (int i = 0; i < n; i++) st[i][0] = a[i];
    for (int k = 2, l = 1; k <= n; k *= 2, l++) {
        for (int i = 0; i + k <= n; i++) {
            st[i][l] = max(st[i][l-1], st[i + k / 2][l-1]);
        }
    }
}

int qry_max(int l, int r) {
    int len = r - l + 1;
    int use = 31 - __builtin_clz(len);
    return max(st[l][use], st[r - (1 << use) + 1][use]);
}

void init(int _n, vector<int> H) {
    n = _n;
    for (int i = 0; i < n; i++) {
        a[i] = H[i];
    }
    build_rmq();

    set<int> s;
    for (int i = 0; i < n; i++) {
        bool use = 1;
        if (i && a[i-1] < a[i]) use = 0;
        if (i < n-1 && a[i+1] < a[i]) use = 0;
        if (use) s.insert(i);
    }
    base = vector<int>(s.begin(), s.end());

    auto f = [&](int i) {
        auto it = s.lower_bound(i); assert(*it == i);
        --it;
        return qry_max(*it, i) - max(a[*it], a[i]);
    };

    set<pair<int, int>> q;
    auto get_v = [&](int x) {
        return pair<int, int>{f(x), x};
    };

    for (auto it = next(s.begin()); it != s.end(); it++) {
        q.insert(get_v(*it));
    }

    vector<pair<int, int>> v;
    v.emplace_back(0, sz(s)); // d > 0, ans = sz(s)
    while (sz(q)) {
        auto [d, i] = *q.begin(); q.erase(q.begin());
        v.emplace_back(d, -1); // need to update v.back().second

        auto it = s.lower_bound(i); assert(*it == i);
        int one = i;
        int two = *prev(it);
        if (next(it) != s.end()) {
            q.erase(get_v(*next(it)));
        }

        if (prev(it) != s.begin()) {
            q.erase(get_v(two));
        }

        if (a[one] > a[two]) {
            s.erase(one);
            ord.push_back(one);
            it = s.lower_bound(two);
            if (next(it) != s.end()) {
                q.insert(get_v(*next(it)));
            }
            if (it != s.begin()) {
                q.insert(get_v(*it));
            }
        } else {
            s.erase(two);
            ord.push_back(two);
            it = s.lower_bound(one);
            if (next(it) != s.end()) {
                q.insert(get_v(*next(it)));
            }
            if (it != s.begin()) {
                q.insert(get_v(*it));
            }
        }

        v.back().second = sz(s);
    }

    store.push_back(v[0]);
    for (int i = 1; i < sz(v); i++) {
        if (v[i].first <= store.back().first) {
            store.back().second = v[i].second;
        } else {
            store.push_back(v[i]);
        }
    }
}

bool has[N];
int max_towers(int l, int r, int d) {
    // find the last thing < d
    int idx = lower_bound(store.begin(), store.end(), pair<int, int>{d, -1}) - store.begin() - 1;
    int gone = sz(base) - store[idx].second;

    memset(has, 0, sizeof(has));
    for (int x : base) has[x] = 1;
    // cerr << "> " << gone << endl;
    for (int i = 0; i < gone; i++) has[ord[i]] = 0;

    int ans = 0;
    int first = n, last = -1;
    for (int i = l; i <= r; i++) {
        ans += has[i];
        if (has[i]) {
            first = min(first, i);
            last = max(last, i);
            // cerr << i << ' ';
        }
    }
    // cerr << endl;

    if (ans == 0) {
        int mx = qry_max(l, r);
        return max(1, (mx - d >= a[l]) + (mx - d >= a[r]));
    }

    /*
    bool one = 0, two = 0;
    for (int i = l; i < first; i++) {
        for (int j = i+1; j < first; j++) {
            if (a[i] <= a[j] - d && a[j] - d >= a[first]) {
                one = 1;
            }
        }
    }

    for (int j = last+1; j <= r; j++) {
        for (int i = j+1; i <= r; i++) {
            if (a[i] <= a[j] - d && a[j] - d >= a[last]) {
                two = 1;
            }
        }
    }

    ans += one;
    ans += two;
    */

    bool one = 0, two = 0;
    if (l < first) one = qry_max(l, first - 1) - d >= a[l];
    if (last < r) two = qry_max(last + 1, r) - d >= a[r];
    return ans + one + two;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 5672 KB Output is correct
2 Correct 2798 ms 9260 KB Output is correct
3 Correct 3115 ms 9288 KB Output is correct
4 Correct 2881 ms 9296 KB Output is correct
5 Correct 2921 ms 9284 KB Output is correct
6 Correct 2895 ms 9296 KB Output is correct
7 Correct 2952 ms 9296 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 592 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Incorrect 2 ms 592 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Incorrect 2 ms 592 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1899 ms 3452 KB Output is correct
2 Execution timed out 4018 ms 13252 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Incorrect 2 ms 592 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 5672 KB Output is correct
2 Correct 2798 ms 9260 KB Output is correct
3 Correct 3115 ms 9288 KB Output is correct
4 Correct 2881 ms 9296 KB Output is correct
5 Correct 2921 ms 9284 KB Output is correct
6 Correct 2895 ms 9296 KB Output is correct
7 Correct 2952 ms 9296 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 592 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 2 ms 592 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 592 KB Output is correct
17 Incorrect 2 ms 592 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
18 Halted 0 ms 0 KB -