Submission #1066287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066287		j_vdd16	Radio Towers (IOI22_towers)	C++17	23 / 100	4067 ms	200384 KiB

towers

#include "towers.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

typedef uint64_t u64;
typedef int64_t i64;


struct MSTree {
    int n, N;

    typedef map<int, int, greater<int>> Entry;
    vector<Entry> tree;

    MSTree() = default;
    MSTree(const vi& values) {
        n = values.size();
        N = 1;
        while (N < n) N *= 2;

        tree = vector<Entry>(2 * N);

        loop(i, n) {
            tree[N + i] = {{values[i], 1}};
        }
        for (int i = N - 1; i >= 1; i--) {
            tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
        }
    }

    Entry merge(const Entry& a, const Entry& b) {
        Entry out;

        auto it1 = a.begin();
        auto it2 = b.begin();
        int pref1 = 0;
        int pref2 = 0;
        
        while (it1 != a.end() && it2 != b.end()) {
            if (it1->first > it2->first) {
                pref1 = it1->second;
                out[it1->first] = pref1 + pref2;

                it1++;
            }
            else {
                pref2 = it2->second;
                out[it2->first] = pref1 + pref2;

                it2++;
            }
        }

        while (it1 != a.end()) {
            pref1 = it1->second;
            out[it1->first] = pref1 + pref2;

            it1++;
        }
        while (it2 != b.end()) {
            pref2 = it2->second;
            out[it2->first] = pref1 + pref2;

            it2++;
        }

        return out;
    }

    int range(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1) tr = N;

        if (l <= tl && r >= tr) {
            auto it = tree[i].upper_bound(v);
            if (it == tree[i].begin())
                return 0;
            
            return (--it)->second;
        }

        if (tl >= r || tr <= l) {
            return 0;
        }

        int tm = (tl + tr) / 2;
        return range(l, r, v, i * 2, tl, tm) + range(l, r, v, i * 2 + 1, tm, tr);
    }
    int leftMost(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1) tr = N;

        if (tl >= r || tr <= l) {
            return -1;
        }

        if (tr - tl == 1) {
            auto it = tree[i].upper_bound(v);
            if (it == tree[i].begin())
                return -1;

            return tl;
        }

        int tm = (tl + tr) / 2;
        int val1 = leftMost(l, r, v, i * 2, tl, tm);
        if (val1 >= 0)
            return val1;

        return leftMost(l, r, v, i * 2 + 1, tm, tr);
    }
    int rightMost(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1) tr = N;

        if (tl >= r || tr <= l) {
            return -1;
        }

        if (tr - tl == 1) {
            auto it = tree[i].upper_bound(v);
            if (it == tree[i].begin())
                return -1;

            return tl;
        }

        int tm = (tl + tr) / 2;
        int val1 = rightMost(l, r, v, i * 2 + 1, tm, tr);
        if (val1 >= 0)
            return val1;

        return rightMost(l, r, v, i * 2, tl, tm);
    }
};
struct SparseTable {
    int n;
    vii table[17];
    vi values;

    SparseTable(const vi& _values) {
        n = _values.size();
        values = _values;

        table[0] = vii(n);
        for (int i = 0; i < n; i++) {
            table[0][i] = { i, i };
        }
        for (int pow = 1; pow < 17; pow++) {
            if (n - (1 << pow) + 1 <= 0) 
                break;

            table[pow] = vii(n - (1 << pow) + 1);
            for (int i = 0; i + (1 << pow) <= n; i++) {
                ii v1 = table[pow - 1][i];
                ii v2 = table[pow - 1][i + (1 << pow) / 2];
                if (values[v1.first] < values[v2.first]) {
                    table[pow][i].first = v1.first;
                }
                else {
                    table[pow][i].first = v2.first;
                }
                if (values[v1.second] > values[v2.second]) {
                    table[pow][i].second = v1.second;
                }
                else {
                    table[pow][i].second = v2.second;
                }
            }
        }
    }

    int minIdx(int l, int r) {
        int exp = 0;
        while ((1 << exp) * 2 <= r - l + 1)
            exp++;

        int pow = 1 << exp;

        ii v1 = table[exp][l];
        ii v2 = table[exp][r - pow + 1];
        if (values[v1.first] < values[v2.first]) {
            return v1.first;
        }
        else {
            return v2.first;
        }
    }
    int maxIdx(int l, int r) {
        int exp = 0;
        while ((1 << exp) * 2 <= r - l + 1)
            exp++;

        int pow = 1 << exp;

        ii v1 = table[exp][l];
        ii v2 = table[exp][r - pow + 1];
        if (values[v1.second] > values[v2.second]) {
            return v1.second;
        }
        else {
            return v2.second;
        }
    }
};

int n;
vi h;

vi bestD, bestLeftD, bestRightD;
MSTree allD, leftD, rightD;
void init(int N, std::vector<int> H) {
    //all H[i] are different
    //dp[i] = max of 1 and all dp[j] over j s.t. j < i && maxH(j, i) - D >= max(H[i], H[j])

    //D = 1
    //H = 1, 2, 6, 4, 5, 3, 7
    //dp= 1, 1, 1, 2, 2, 3, 1

    //count no. of i for which there exist l, r such that h[i] = minH[l, r] && h[i] + D <= h[l], h[r]

    n = N;
    h = H;

    if (n == 1) return;

    SparseTable sparse(H);
    sparse.minIdx(1, 1);

    bestD = vi(n), bestLeftD = vi(n), bestRightD = vi(n);
    loop(i, n) {
        int minLeft, minRight;
        {
            int l = -1, r = i - 1;
            while (l < r) {
                int m = (l + r + 1) / 2;

                int minIdx = sparse.minIdx(m, r);
                if (h[minIdx] < h[i]) {
                    l = m;
                }
                else {
                    r = m - 1;
                }
            }
            minLeft = l;
        }
        {
            int l = i + 1, r = n;
            while (l < r) {
                int m = (l + r) / 2;

                int minIdx = sparse.minIdx(l, m);
                if (h[minIdx] < h[i]) {
                    r = m;
                }
                else {
                    l = m + 1;
                }
            }
            minRight = r;
        }

        //cout << i << ' ' << minLeft << ' ' << minRight << endl;
        if (minLeft + 1 <= i - 1 && minRight - 1 >= i + 1) {
            bestD[i] = min(h[sparse.maxIdx(minLeft + 1, i - 1)], h[sparse.maxIdx(i + 1, minRight - 1)]) - h[i];
        }

        if (minRight - 1 >= i + 1) {
            bestLeftD[i] = h[sparse.maxIdx(i + 1, minRight - 1)] - h[i];
        }
        if (minLeft + 1 <= i - 1) {
            bestRightD[i] = h[sparse.maxIdx(minLeft + 1, i - 1)] - h[i];
        }
    }

    allD = MSTree(bestD);
    leftD = MSTree(bestLeftD);
    rightD = MSTree(bestRightD);
}

int max_towers(int L, int R, int D) {
    if (L == R) {
        return 1;
    }

    int left = leftD.leftMost(L, R + 1, D);
    int right = rightD.rightMost(L, R + 1, D);
    if (left == -1 || right == -1 || left + 1 > right - 1) {
        return 1;
    }

    int extra = allD.range(left + 1, right - 1 + 1, D);
    return 2 + extra;
}

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23