Submission #1055351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055351		vjudge1	Radio Towers (IOI22_towers)	C++17	23 / 100	4056 ms	7888 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

int n;
vi H, Hord;

map<int, int> NorMap;

void init(int n, vi H0) {
    ::n = n;
    H = H0;
    Hord = H;
    sort(Hord.begin(), Hord.end());
    Hord.resize(unique(Hord.begin(), Hord.end()) - Hord.begin());
    for(int i = 0; i < (int)Hord.size(); ++i) 
        NorMap[Hord[i]] = i;
}

struct AIB { // max pe prefixe
    int n;
    vi V;
    AIB(int N) : n(N + 2), V(N + 2, -1) {}

    void update(int p, int v) {
        ++p;
        while(p < n) {
            V[p] = max(V[p], v);
            p += p & -p;
        }
    }

    int query(int p) {
        ++p;
        if( p < 0 ) return 0;
        int re = 0;
        while(p) {
            re = max(re, V[p]);
            p -= p & -p;
        }
        return re;
    }
};

struct maxSuf {
    int n;
    AIB A;
    maxSuf(int N) : n(N + 1), A(N + 1) {}

    void update(int p, int v) { A.update(n - p - 1, v); }
    int query(int p) { return A.query(n - p - 1); }
};

int max_towers(int l, int r, int D) {
    vi DP0(n, 1), DP1(n, 0);
    ///DP0, ult e statie. DP1 ult e turn

    AIB MP(n);
    maxSuf MS(n);
    int re = 1;

    for (int i = l; i <= r; ++i) {
        int y = H[i];
        if(Hord[0] + D <= y) { /// merita cautat
            //leg un turn la ceva mai mic
            int st = 0, dr = int(Hord.size()) - 1, mij;
            while(st < dr) {
                mij = (st + dr + 1) / 2;
                if(Hord[mij] + D <= y) st = mij;
                else dr = mij - 1;
            }
            DP1[i] = max(DP1[i], 1 + MP.query(st));
        }
        MS.update(NorMap[y], DP1[i]);
        if(Hord.back() - D >= y) {
            int st = 0, dr = int(Hord.size()) - 1, mij;
            while(st < dr) {
                mij = (st + dr) / 2;
                if(Hord[mij] - D >= y) {
                    dr = mij;
                } else st = mij + 1;
            }
            DP0[i] = max(DP0[i], MS.query(st) + 1);
        }
        MP.update(NorMap[y], DP0[i]);
        re = max(re, (DP0[i] + 1) / 2);
    }
    return re;
}

• 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