Submission #1210758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210758		qwusha	Radio Towers (IOI22_towers)	C++20	23 / 100	4054 ms	6516 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e9;

int n;
vector<int> h;
vector<int> num;
vector<int> bigger;
vector<int> smaller;

struct segtree{
    int sz = 1;
    vector<int> tree;
    void init() {
        while(sz < n) {
            sz <<= 1;
        }
        tree.assign(sz * 2 - 1, 0);
    }
    void update(int ind, int newq) {
        upd(0,0,sz,ind,newq);
    }
    void upd(int v, int l, int r, int ind, int newq) {
        if (r - l == 1) {
            tree[v] = newq;
            return;
        }
        int m = (l + r) / 2;
        if (ind < m) {
            upd(v * 2 + 1, l, m, ind, newq);
        } else {
            upd(v * 2 + 2, m, r, ind, newq);
        }
        tree[v] = max(tree[v * 2 + 1] , tree[v * 2 + 2]);
    }
    int answer(int lq, int rq) {
        return ans(0,0,sz, lq, rq);
    }
    int ans(int v, int l, int r, int lq, int rq) {
        if (lq <= l && r <= rq) {
            return tree[v];
        }
        if (lq >= r || rq <= l) {
            return 0;
        }
        int m = (l + r) / 2;
        int a1 = ans(v * 2 + 1, l, m, lq, rq),
        a2 = ans(v * 2 + 2, m, r, lq, rq);
        return max(a1, a2);
    }
};


void init(int N, vector<int> H) {
    n = N;
    h = H;
}

int max_towers(int l, int r, int d) {
    num.assign(n, 0);
    bigger.assign(n, 0);
    smaller.assign(n, 0);
    vector<pair<int, int>> vec;
    for (int i= 0 ; i < n; i++) {
        vec.push_back({h[i], i});
    }
    sort(vec.begin(), vec.end());
    for (int i = 0; i < n; i++) {
        num[vec[i].se] = i;
        smaller[i] = -1;
        bigger[i] = inf;
        int l = 0, r = i;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (vec[mid].fi + d <= vec[i].fi) {
                l = mid;
            } else {
                r = mid;
            }
        }
        if (vec[l].fi + d <= vec[i].fi) {
            smaller[i] = l;
        }
        l = i, r = n - 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (vec[i].fi + d <= vec[mid].fi) {
                r = mid;
            } else {
                l = mid;
            }
        }
        if (vec[i].fi + d <= vec[r].fi) {
            bigger[i] = r;
        }
    }
    segtree treefi, treese;
    treefi.init();
    treese.init();

    vector<pair<int, int>> dp(n, {1, 0});
    int res = 0;
    for (int i = l; i <= r; i++) {
        int ind = num[i];
        if (smaller[ind] != -1) {
            dp[i].se = max(dp[i].se, treefi.answer(0, smaller[ind] + 1));
            treese.update(ind, dp[i].se);
        }
        if (bigger[ind] != inf) {
            dp[i].fi = max(dp[i].fi, treese.answer(bigger[ind], n) + 1);
            treefi.update(ind, dp[i].fi);
        }
        res = max(res, dp[i].fi);
    }
    return res;
}

• 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