oj.uz

Submission #771465

# Submission time Handle Problem Language Result Execution time Memory
771465 2023-07-03T03:47:48 Z PurpleCrayon Radio Towers (IOI22_towers) C++17
27 / 100
 4000 ms 62396 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;

struct D1 {
    int sum, mn, mx;

    D1() {
        sum = 0;
        mn = MOD;
        mx = -1;
    }

    D1(int x, int loc) {
        sum = x;
        if (x) mn = mx = loc;
        else mn = MOD, mx = -1;
    }

    friend D1 operator + (const D1& one, const D1& two) {
        D1 ans;
        ans.sum = one.sum + two.sum;
        ans.mn = min(one.mn, two.mn);
        ans.mx = max(one.mx, two.mx);
        return ans;
    }
};

struct T1 {
    D1 d;
    T1 *l, *r;

    T1(D1 _d): d(_d) {
        l = nullptr;
        r = nullptr;
    }

    T1(T1* _l, T1* _r): l(_l), r(_r) {
        d = l->d + r->d;
    }
};

T1* build1(int tl, int tr, const vector<int>& v) {
    if (tl == tr) {
        return new T1(D1(v[tl], tl));
    }
    else {
        int tm = (tl + tr) / 2;
        T1* ans = new T1(build1(tl, tm, v), build1(tm+1, tr, v));
        return ans;
    }
}

T1* upd1(T1* t, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        return new T1(D1(x, tl));
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return new T1(upd1(t->l, tl, tm, pos, x), t->r);
    else
        return new T1(t->l, upd1(t->r, tm+1, tr, pos, x));
}

D1 qry1(T1* t, int tl, int tr, int l, int r) {
    if (r < tl || l > tr) return D1();
    if (l <= tl && tr <= r) return t->d;
    int tm = (tl + tr) / 2;
    return qry1(t->l, tl, tm, l, r) + qry1(t->r, tm+1, tr, l, r);
}

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

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

    vector<int> aux_base(n);
    for (int x : base) aux_base[x] = 1;
    vers[0] = build1(0, n-1, aux_base);
    // cerr << "done\n";
    for (int i = 1; i <= sz(ord); i++) {
        vers[i] = upd1(vers[i-1], 0, n-1, ord[i-1], 0);
    }
    // cerr << "done\n";
}

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;

    D1 dd = qry1(vers[gone], 0, n-1, l, r);
    int ans = dd.sum;
    int first = dd.mn, last = dd.mx;

    /*
    memset(has, 0, sizeof(has));
    for (int x : base) has[x] = 1;
    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 << ans << ' ' << ' ' << first << ' ' << last << 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++) {
        int x = qry_max(i, first);
        if (a[i] <= x - d && x - d >= a[first]) {
            one = 1;
            break;
        }
    }

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

    ans += one;
    ans += two;

    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 11492 KB Output is correct
2 Correct 825 ms 19036 KB Output is correct
3 Correct 809 ms 19024 KB Output is correct
4 Correct 792 ms 19024 KB Output is correct
5 Correct 788 ms 18988 KB Output is correct
6 Correct 651 ms 19024 KB Output is correct
7 Correct 853 ms 19064 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 2 ms 976 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 2 ms 1232 KB Output is correct
6 Correct 2 ms 1232 KB Output is correct
7 Correct 2 ms 1232 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 2 ms 1104 KB Output is correct
16 Correct 3 ms 1232 KB Output is correct
17 Correct 3 ms 1232 KB Output is correct
18 Correct 1 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 2 ms 976 KB Output is correct
21 Correct 2 ms 1232 KB Output is correct
22 Correct 2 ms 1232 KB Output is correct
23 Correct 1 ms 648 KB Output is correct
24 Correct 1 ms 592 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 2 ms 1104 KB Output is correct
27 Correct 2 ms 976 KB Output is correct
28 Correct 2 ms 1232 KB Output is correct
29 Correct 2 ms 1232 KB Output is correct
30 Correct 3 ms 1232 KB Output is correct
31 Correct 3 ms 1232 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 592 KB Output is correct
34 Correct 1 ms 592 KB Output is correct
35 Correct 1 ms 592 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 2 ms 976 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 2 ms 1232 KB Output is correct
6 Correct 2 ms 1232 KB Output is correct
7 Correct 2 ms 1232 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 2 ms 1104 KB Output is correct
16 Correct 3 ms 1232 KB Output is correct
17 Correct 3 ms 1232 KB Output is correct
18 Correct 1 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 2 ms 976 KB Output is correct
21 Correct 2 ms 1232 KB Output is correct
22 Correct 2 ms 1232 KB Output is correct
23 Correct 1 ms 648 KB Output is correct
24 Correct 1 ms 592 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 2 ms 1104 KB Output is correct
27 Correct 2 ms 976 KB Output is correct
28 Correct 2 ms 1232 KB Output is correct
29 Correct 2 ms 1232 KB Output is correct
30 Correct 3 ms 1232 KB Output is correct
31 Correct 3 ms 1232 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 592 KB Output is correct
34 Correct 1 ms 592 KB Output is correct
35 Correct 1 ms 592 KB Output is correct
36 Correct 79 ms 30448 KB Output is correct
37 Correct 137 ms 48216 KB Output is correct
38 Correct 126 ms 48000 KB Output is correct
39 Correct 192 ms 62248 KB Output is correct
40 Correct 184 ms 62300 KB Output is correct
41 Correct 183 ms 62228 KB Output is correct
42 Correct 201 ms 62284 KB Output is correct
43 Correct 22 ms 19024 KB Output is correct
44 Correct 22 ms 19016 KB Output is correct
45 Correct 21 ms 19016 KB Output is correct
46 Correct 22 ms 19032 KB Output is correct
47 Correct 127 ms 47988 KB Output is correct
48 Correct 199 ms 62272 KB Output is correct
49 Correct 187 ms 62220 KB Output is correct
50 Correct 21 ms 19024 KB Output is correct
51 Correct 21 ms 19032 KB Output is correct
52 Correct 131 ms 47932 KB Output is correct
53 Correct 184 ms 62308 KB Output is correct
54 Correct 194 ms 62396 KB Output is correct
55 Correct 22 ms 19032 KB Output is correct
56 Correct 25 ms 19052 KB Output is correct
57 Correct 144 ms 46044 KB Output is correct
58 Correct 130 ms 48064 KB Output is correct
59 Correct 130 ms 48220 KB Output is correct
60 Correct 184 ms 62316 KB Output is correct
61 Correct 182 ms 62248 KB Output is correct
62 Correct 206 ms 62232 KB Output is correct
63 Correct 193 ms 62304 KB Output is correct
64 Correct 28 ms 19016 KB Output is correct
65 Correct 22 ms 19040 KB Output is correct
66 Correct 22 ms 18984 KB Output is correct
67 Correct 22 ms 19016 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 47624 KB Output is correct
2 Correct 809 ms 48056 KB Output is correct
3 Correct 1026 ms 48068 KB Output is correct
4 Correct 1064 ms 62236 KB Output is correct
5 Correct 1092 ms 62200 KB Output is correct
6 Correct 978 ms 62252 KB Output is correct
7 Correct 965 ms 62296 KB Output is correct
8 Correct 725 ms 18976 KB Output is correct
9 Correct 856 ms 18988 KB Output is correct
10 Execution timed out 4035 ms 19016 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 10888 KB Output is correct
2 Correct 942 ms 48044 KB Output is correct
3 Correct 886 ms 48028 KB Output is correct
4 Correct 816 ms 62276 KB Output is correct
5 Correct 930 ms 62276 KB Output is correct
6 Correct 891 ms 62268 KB Output is correct
7 Correct 842 ms 62276 KB Output is correct
8 Execution timed out 4018 ms 18972 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 2 ms 976 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 2 ms 1232 KB Output is correct
6 Correct 2 ms 1232 KB Output is correct
7 Correct 2 ms 1232 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 0 ms 208 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 2 ms 1104 KB Output is correct
16 Correct 3 ms 1232 KB Output is correct
17 Correct 3 ms 1232 KB Output is correct
18 Correct 1 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 2 ms 976 KB Output is correct
21 Correct 2 ms 1232 KB Output is correct
22 Correct 2 ms 1232 KB Output is correct
23 Correct 1 ms 648 KB Output is correct
24 Correct 1 ms 592 KB Output is correct
25 Correct 1 ms 592 KB Output is correct
26 Correct 2 ms 1104 KB Output is correct
27 Correct 2 ms 976 KB Output is correct
28 Correct 2 ms 1232 KB Output is correct
29 Correct 2 ms 1232 KB Output is correct
30 Correct 3 ms 1232 KB Output is correct
31 Correct 3 ms 1232 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 1 ms 592 KB Output is correct
34 Correct 1 ms 592 KB Output is correct
35 Correct 1 ms 592 KB Output is correct
36 Correct 79 ms 30448 KB Output is correct
37 Correct 137 ms 48216 KB Output is correct
38 Correct 126 ms 48000 KB Output is correct
39 Correct 192 ms 62248 KB Output is correct
40 Correct 184 ms 62300 KB Output is correct
41 Correct 183 ms 62228 KB Output is correct
42 Correct 201 ms 62284 KB Output is correct
43 Correct 22 ms 19024 KB Output is correct
44 Correct 22 ms 19016 KB Output is correct
45 Correct 21 ms 19016 KB Output is correct
46 Correct 22 ms 19032 KB Output is correct
47 Correct 127 ms 47988 KB Output is correct
48 Correct 199 ms 62272 KB Output is correct
49 Correct 187 ms 62220 KB Output is correct
50 Correct 21 ms 19024 KB Output is correct
51 Correct 21 ms 19032 KB Output is correct
52 Correct 131 ms 47932 KB Output is correct
53 Correct 184 ms 62308 KB Output is correct
54 Correct 194 ms 62396 KB Output is correct
55 Correct 22 ms 19032 KB Output is correct
56 Correct 25 ms 19052 KB Output is correct
57 Correct 144 ms 46044 KB Output is correct
58 Correct 130 ms 48064 KB Output is correct
59 Correct 130 ms 48220 KB Output is correct
60 Correct 184 ms 62316 KB Output is correct
61 Correct 182 ms 62248 KB Output is correct
62 Correct 206 ms 62232 KB Output is correct
63 Correct 193 ms 62304 KB Output is correct
64 Correct 28 ms 19016 KB Output is correct
65 Correct 22 ms 19040 KB Output is correct
66 Correct 22 ms 18984 KB Output is correct
67 Correct 22 ms 19016 KB Output is correct
68 Correct 666 ms 47624 KB Output is correct
69 Correct 809 ms 48056 KB Output is correct
70 Correct 1026 ms 48068 KB Output is correct
71 Correct 1064 ms 62236 KB Output is correct
72 Correct 1092 ms 62200 KB Output is correct
73 Correct 978 ms 62252 KB Output is correct
74 Correct 965 ms 62296 KB Output is correct
75 Correct 725 ms 18976 KB Output is correct
76 Correct 856 ms 18988 KB Output is correct
77 Execution timed out 4035 ms 19016 KB Time limit exceeded
78 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 11492 KB Output is correct
2 Correct 825 ms 19036 KB Output is correct
3 Correct 809 ms 19024 KB Output is correct
4 Correct 792 ms 19024 KB Output is correct
5 Correct 788 ms 18988 KB Output is correct
6 Correct 651 ms 19024 KB Output is correct
7 Correct 853 ms 19064 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 2 ms 976 KB Output is correct
13 Correct 2 ms 976 KB Output is correct
14 Correct 3 ms 1280 KB Output is correct
15 Correct 2 ms 1232 KB Output is correct
16 Correct 2 ms 1232 KB Output is correct
17 Correct 2 ms 1232 KB Output is correct
18 Correct 1 ms 592 KB Output is correct
19 Correct 1 ms 592 KB Output is correct
20 Correct 1 ms 592 KB Output is correct
21 Correct 1 ms 592 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 1 ms 592 KB Output is correct
24 Correct 1 ms 592 KB Output is correct
25 Correct 2 ms 1104 KB Output is correct
26 Correct 3 ms 1232 KB Output is correct
27 Correct 3 ms 1232 KB Output is correct
28 Correct 1 ms 592 KB Output is correct
29 Correct 1 ms 592 KB Output is correct
30 Correct 2 ms 976 KB Output is correct
31 Correct 2 ms 1232 KB Output is correct
32 Correct 2 ms 1232 KB Output is correct
33 Correct 1 ms 648 KB Output is correct
34 Correct 1 ms 592 KB Output is correct
35 Correct 1 ms 592 KB Output is correct
36 Correct 2 ms 1104 KB Output is correct
37 Correct 2 ms 976 KB Output is correct
38 Correct 2 ms 1232 KB Output is correct
39 Correct 2 ms 1232 KB Output is correct
40 Correct 3 ms 1232 KB Output is correct
41 Correct 3 ms 1232 KB Output is correct
42 Correct 1 ms 592 KB Output is correct
43 Correct 1 ms 592 KB Output is correct
44 Correct 1 ms 592 KB Output is correct
45 Correct 1 ms 592 KB Output is correct
46 Correct 79 ms 30448 KB Output is correct
47 Correct 137 ms 48216 KB Output is correct
48 Correct 126 ms 48000 KB Output is correct
49 Correct 192 ms 62248 KB Output is correct
50 Correct 184 ms 62300 KB Output is correct
51 Correct 183 ms 62228 KB Output is correct
52 Correct 201 ms 62284 KB Output is correct
53 Correct 22 ms 19024 KB Output is correct
54 Correct 22 ms 19016 KB Output is correct
55 Correct 21 ms 19016 KB Output is correct
56 Correct 22 ms 19032 KB Output is correct
57 Correct 127 ms 47988 KB Output is correct
58 Correct 199 ms 62272 KB Output is correct
59 Correct 187 ms 62220 KB Output is correct
60 Correct 21 ms 19024 KB Output is correct
61 Correct 21 ms 19032 KB Output is correct
62 Correct 131 ms 47932 KB Output is correct
63 Correct 184 ms 62308 KB Output is correct
64 Correct 194 ms 62396 KB Output is correct
65 Correct 22 ms 19032 KB Output is correct
66 Correct 25 ms 19052 KB Output is correct
67 Correct 144 ms 46044 KB Output is correct
68 Correct 130 ms 48064 KB Output is correct
69 Correct 130 ms 48220 KB Output is correct
70 Correct 184 ms 62316 KB Output is correct
71 Correct 182 ms 62248 KB Output is correct
72 Correct 206 ms 62232 KB Output is correct
73 Correct 193 ms 62304 KB Output is correct
74 Correct 28 ms 19016 KB Output is correct
75 Correct 22 ms 19040 KB Output is correct
76 Correct 22 ms 18984 KB Output is correct
77 Correct 22 ms 19016 KB Output is correct
78 Correct 666 ms 47624 KB Output is correct
79 Correct 809 ms 48056 KB Output is correct
80 Correct 1026 ms 48068 KB Output is correct
81 Correct 1064 ms 62236 KB Output is correct
82 Correct 1092 ms 62200 KB Output is correct
83 Correct 978 ms 62252 KB Output is correct
84 Correct 965 ms 62296 KB Output is correct
85 Correct 725 ms 18976 KB Output is correct
86 Correct 856 ms 18988 KB Output is correct
87 Execution timed out 4035 ms 19016 KB Time limit exceeded
88 Halted 0 ms 0 KB -