oj.uz

Submission #1060892

# Submission time Handle Problem Language Result Execution time Memory
1060892 2024-08-16T04:07:23 Z becaido Radio Towers (IOI22_towers) C++17
17 / 100
 4000 ms 75556 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "towers.h"
#else
#include "stub.cpp"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int INF = 2e9 + 1;
const int SIZE = 1e5 + 5;

int n;
int a[SIZE], ty[SIZE];

struct Segtree {
    struct T {
        int mx, mn, ld, rd;
        T operator + (const T &o) const {
            T re;
            re.mx = max(mx, o.mx);
            re.mn = min(mn, o.mn);
            re.ld = max({ld, o.ld, o.mx - mn});
            re.rd = max({rd, o.rd, mx - o.mn});
            return re;
        }
    } node[SIZE << 2];

    void build(int pos, int l, int r) {
        if (l == r) {
            node[pos].mx = node[pos].mn = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(lpos, l, mid);
        build(rpos, mid + 1, r);
        node[pos] = node[lpos] + node[rpos];
    }
    int schl(int pos, int l, int r, int L, int R, int x) {
        if (l == L && r == R) {
            if (node[pos].mx < x) return 0;
            if (l == r) return l;
            int mid = (L + R) / 2, re = schl(lpos, l, mid, L, mid, x);
            return re == 0 ? schl(rpos, mid + 1, r, mid + 1, R, x) : re;
        }
        int mid = (L + R) / 2, re;
        if (r <= mid) return schl(lpos, l, r, L, mid, x);
        if (l > mid) return schl(rpos, l, r, mid + 1, R, x);
        re = schl(lpos, l, mid, L, mid, x);
        return re == 0 ? schl(rpos, mid + 1, r, mid + 1, R, x) : re;
    }
    int schr(int pos, int l, int r, int L, int R, int x) {
        if (l == L && r == R) {
            if (node[pos].mx < x) return 0;
            if (l == r) return l;
            int mid = (L + R) / 2, re = schr(rpos, mid + 1, r, mid + 1, R, x);
            return re == 0 ? schr(lpos, l, mid, L, mid, x) : re;
        }
        int mid = (L + R) / 2, re;
        if (r <= mid) return schr(lpos, l, r, L, mid, x);
        if (l > mid) return schr(rpos, l, r, mid + 1, R, x);
        re = schr(rpos, mid + 1, r, mid + 1, R, x);
        return re == 0 ? schr(lpos, l, mid, L, mid, x) : re;
    }
    T que(int pos, int l, int r, int L, int R) {
        if (l == L && r == R) return node[pos];
        int mid = (L + R) / 2;
        if (r <= mid) return que(lpos, l, r, L, mid);
        if (l > mid) return que(rpos, l, r, mid + 1, R);
        return que(lpos, l, mid, L, mid) + que(rpos, mid + 1, r, mid + 1, R);
    }
} tree;

struct Node {
    int cnt, pcnt, ls, rs;
} node[2 * SIZE * (__lg(SIZE) + 3)];

int sz, root;
vector<pair<int, int>> vroot;
void upd(int &pos, int l, int r, int p, int t, int x) {
    node[++sz] = node[pos];
    pos = sz;
    (t == 1 ? node[pos].cnt : node[pos].pcnt) += x;
    if (l == r) return;
    int mid = (l + r) / 2;
    if (p <= mid) upd(node[pos].ls, l, mid, p, t, x);
    else upd(node[pos].rs, mid + 1, r, p, t, x);
}
int que(int pos, int l, int r, int L, int R, int t) {
    if (l == L && r == R) return t == 1 ? node[pos].cnt : node[pos].pcnt;
    int mid = (L + R) / 2;
    if (r <= mid) return que(node[pos].ls, l, r, L, mid, t);
    if (l > mid) return que(node[pos].rs, l, r, mid + 1, R, t);
    return que(node[pos].ls, l, mid, L, mid, t) + que(node[pos].rs, mid + 1, r, mid + 1, R, t);
}
int sch(int pos, int l, int r, int t, int k) {
    int tot = (t ? node[pos].cnt : node[pos].pcnt);
    if (k > tot) return 0;
    if (l == r) return l;
    int mid = (l + r) / 2, ltot = (t ? node[node[pos].ls].cnt : node[node[pos].ls].pcnt);
    return k <= ltot ? sch(node[pos].ls, l, mid, t, k) : sch(node[pos].rs, mid + 1, r, t, k - ltot);
}

void init(int N, vector<int> H) {
    n = N;
    if (n == 1) return;
    FOR (i, 1, n) a[i] = H[i - 1];
    FOR (i, 1, n) {
        if ((i == 1 || a[i] < a[i - 1]) && (i == n || a[i] < a[i + 1])) ty[i] = 1;
        if ((i == 1 || a[i] > a[i - 1]) && (i == n || a[i] > a[i + 1])) ty[i] = 2;
    }

    set<int> s;
    multiset<pair<int, int>> ms;
    for (int i = 1, x = 1; i <= n; i++) if (ty[i] == x) {
        s.insert(i);
        x ^= 3;
    }
    if (ty[*s.rbegin()] == 2) s.erase(*s.rbegin());
    a[0] = a[n + 1] = INF;
    s.insert(0), s.insert(n + 1);
    bool f = 0;
    for (auto it = s.begin(); it != s.end(); it++) {
        f ^= 1;
        if (f == 0) continue;
        int i = *it;
        if (it != s.begin()) {
            int l = *prev(it);
            ms.emplace(a[i] - a[l], i);
        }
        if (next(it) != s.end()) {
            int r = *next(it);
            ms.emplace(a[i] - a[r], i);
        }
    }
    for (int i : s) if (ty[i]) upd(root, 1, n, i, ty[i], 1);
    vroot.pb(0, root);
    while (s.size() > 3) {
        int d = ms.begin()->F;
        while (ms.size() && ms.begin()->F == d) {
            auto [_, i] = *ms.begin();
            auto it = s.lower_bound(i), lit = prev(it), rit = next(it);
            int l = *lit, r = *rit;
            int il = *prev(lit), ir = *next(rit);
            if (a[l] > a[r]) {
                ms.erase(ms.find({a[i] - a[l], i}));
                ms.erase(ms.find({a[il] - a[l], il}));
                if (a[i] < a[il]) {
                    ms.erase({a[i] - a[r], i});
                    ms.emplace(a[il] - a[r], il);
                    s.erase(i), upd(root, 1, n, i, 2, -1);
                } else {
                    int j = *prev(s.find(il));
                    ms.erase(ms.find({a[il] - a[j], il}));
                    ms.emplace(a[i] - a[j], i);
                    s.erase(il), upd(root, 1, n, il, 2, -1);
                }
                s.erase(l), upd(root, 1, n, l, 1, -1);
            } else {
                ms.erase(ms.find({a[i] - a[r], i}));
                ms.erase(ms.find({a[ir] - a[r], ir}));
                if (a[i] < a[ir]) {
                    ms.erase({a[i] - a[l], i});
                    ms.emplace(a[ir] - a[l], ir);
                    s.erase(i), upd(root, 1, n, i, 2, -1);
                } else {
                    int j = *next(s.find(ir));
                    ms.erase(ms.find({a[ir] - a[j], ir}));
                    ms.emplace(a[i] - a[j], i);
                    s.erase(ir), upd(root, 1, n, ir, 2, -1);
                }
                s.erase(r), upd(root, 1, n, r, 1, -1);
            }
        }
        vroot.pb(d + 1, root);
    }
    tree.build(1, 1, n);
}

int max_towers(int L, int R, int D) {
    L++, R++;
    if (L == R) return 1;
    root = (lower_bound(vroot.begin(), vroot.end(), make_pair(D + 1, 0)) - 1)->S;
    int ans = que(root, L, R, 1, n, 1);
    if (ans == 0) {
        int pcnt = que(root, L, R, 1, n, 2);
        if (pcnt == 0) return 1;
        int i = sch(root, 1, n, 2, L == 1 ? 1 : que(root, 1, L - 1, 1, n, 2) + 1);
        return 1 + (tree.que(1, L, i, 1, n).mn + D <= a[i] && tree.que(1, i, R, 1, n).mn + D <= a[i]);
    }
    {
        int i = sch(root, 1, n, 1, L == 1 ? 1 : que(root, 1, L - 1, 1, n, 1) + 1);
        int j = tree.schr(1, L, i, 1, n, a[i] + D);
        if (j) ans += (tree.que(1, L, j, 1, n).ld >= D);
    }
    {
        int i = sch(root, 1, n, 1, que(root, 1, R, 1, n, 1));
        int j = tree.schl(1, i, R, 1, n, a[i] + D);
        if (j) ans += (tree.que(1, j, R, 1, n).rd >= D);
    }
    return ans;
}

/*
in1
7 3
10 20 60 40 50 30 70
1 5 10
2 2 100
0 6 17
out1
3
1
2
*/

Subtask #1
0 / 4.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6724 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Execution timed out 4080 ms 4440 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6724 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Execution timed out 4080 ms 4440 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 16880 KB Output is correct
2 Correct 826 ms 53992 KB Output is correct
3 Correct 838 ms 53640 KB Output is correct
4 Correct 894 ms 75464 KB Output is correct
5 Correct 915 ms 75484 KB Output is correct
6 Correct 908 ms 75512 KB Output is correct
7 Correct 896 ms 75464 KB Output is correct
8 Correct 708 ms 9816 KB Output is correct
9 Correct 728 ms 9816 KB Output is correct
10 Correct 665 ms 9816 KB Output is correct
11 Correct 668 ms 9816 KB Output is correct
12 Correct 101 ms 53704 KB Output is correct
13 Correct 159 ms 75460 KB Output is correct
14 Correct 170 ms 75464 KB Output is correct
15 Correct 10 ms 9816 KB Output is correct
16 Correct 10 ms 9816 KB Output is correct
17 Correct 107 ms 53456 KB Output is correct
18 Correct 106 ms 53688 KB Output is correct
19 Correct 107 ms 53712 KB Output is correct
20 Correct 183 ms 75464 KB Output is correct
21 Correct 175 ms 75556 KB Output is correct
22 Correct 168 ms 75392 KB Output is correct
23 Correct 171 ms 75464 KB Output is correct
24 Correct 10 ms 9820 KB Output is correct
25 Correct 9 ms 9796 KB Output is correct
26 Correct 10 ms 9816 KB Output is correct
27 Correct 18 ms 9800 KB Output is correct
28 Correct 2 ms 6744 KB Output is correct
29 Correct 2 ms 6744 KB Output is correct
30 Correct 3 ms 6744 KB Output is correct
31 Correct 1 ms 4440 KB Output is correct
32 Correct 1 ms 4440 KB Output is correct
33 Correct 2 ms 6744 KB Output is correct
34 Correct 2 ms 6744 KB Output is correct
35 Correct 2 ms 6908 KB Output is correct
36 Correct 3 ms 6744 KB Output is correct
37 Correct 3 ms 6956 KB Output is correct
38 Correct 3 ms 6744 KB Output is correct
39 Correct 2 ms 6744 KB Output is correct
40 Correct 1 ms 4440 KB Output is correct
41 Correct 1 ms 4440 KB Output is correct
42 Correct 1 ms 4440 KB Output is correct
43 Correct 1 ms 4440 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6724 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Execution timed out 4080 ms 4440 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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