Построение acmp

Question

https://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=20&id_topic=46&id_problem=601

В одной военной части решили построить солдат в одну шеренгу по росту. Т.к. часть была далеко не образцовая, то солдаты часто приходили не вовремя, а то их и вовсе приходилось выгонять из шеренги за плохо начищенные сапоги. Однако солдаты в процессе прихода и ухода должны были всегда быть выстроены по росту – сначала самые высокие, а в конце – самые низкие. За расстановку солдат отвечал прапорщик, который заметил интересную особенность – все солдаты в части разного роста.

Ваша задача состоит в том, чтобы помочь прапорщику правильно расставлять солдат, а именно для каждого приходящего солдата указывать, перед каким солдатом в строе он должен становится.

Входные данные Первая строка входного файла INPUT.TXT содержит число N – количество команд (1 ≤ N ≤ 30 000). В каждой следующей строке содержится описание команды: число 1 и X, если солдат приходит в строй (X – рост солдата, натуральное число до 100 000 включительно) и число 2 и Y, если солдата, стоящего в строе на месте Y надо удалить из строя (солдаты в строе нумеруются с нуля).

Выходные данные В выходной файл OUTPUT.TXT выведите в отдельной строке для каждой команды 1 (добавление в строй) число K – номер позиции, на которую должен встать этот солдат (все стоящие за ним двигаются назад).

def set1(i, v, x, lx, rx):
    if rx - lx == 1:
        st[x] = v
        return
    m = (lx + rx) // 2
    if i < m:
        set1(i, v, 2 * x + 1, lx, m)
    else:
        set1(i, v, 2 * x + 2, m, rx)
    st[x] = st[x * 2 + 1] + st[x * 2 + 2]


def sum1(l, r, x, lx, rx):
    if l >= rx or lx >= r:
        return 0
    if lx >= l and rx <= r:
        return st[x]
    m = (lx + rx) // 2
    return sum1(l, r, x * 2 + 1, lx, m) + sum1(l, r, x * 2 + 2, m, rx)


def k_(k, x, lx, rx):
    if rx - lx == 1:
        return lx
    m = (lx + rx) // 2
    if st[x * 2 + 1] <= k:
        return k_(k - st[x * 2 + 1], x * 2 + 2, m, rx)
    return k_(k, x * 2 + 1, lx, m)


n = int(input())
N = 100_005
st = [0] * (N * 4)
for _ in range(n):
    i, x = map(int, input().split())
    if i == 1:
        print(sum1(x, N, 0, 0, N))
        set1(x, 1, 0, 0, N)
    else:
        i = k_(x, 0, 0, N)
        set1(i, 0, 0, 0, N)

дерево отрезков.

функция set1 обновляет значение в ДО по индексу

функция sum1 ищет сумму от левой границы до конца

функция k_ ищет индекс в ДО, что бы удалить элемент из ДО

st - дерево отрезков, построенное на принципе максимального и минимального значений. Если мы добавляем солдата, то обновляем ячейку с его ростом в ДО, если убираем k-того солдата, сначала ищем его рост по функции k_, а потом удаляем функцией set1 WA на 4 тесте, в чем ошибка?

Answer 1

Пример:

После первых двух команд в строю 4 2. Следующая команда удаляет солдата с первой позиции. Позиции нумеруются с нуля, строй становится 4. Последняя команда вставляет солдата в конец строя на позицию номер один, чтобы получилось 4 3. Ваша программа для последней команды печатает ноль.

Answer 2

нужно было вычесть из общего количества солдат номер того, которого мы хотим удалить, что бы смотреть именно k-тую единицу с максимальной стороны. На Python решение не проходит, только на C++

#include<bits/stdc++.h>
using namespace std;

int z = 0, n, m, x, i;
vector<int> st(400020, 0);

void set1(int i, int v, int x, int lx, int rx){
    if (rx - lx == 1){
        st[x] = v;
        return;
    }
    m = (lx + rx) / 2;
    if (i < m){
        set1(i, v, 2 * x + 1, lx, m);
    }
    else{
        set1(i, v, 2 * x + 2, m, rx);
    }
    st[x] = st[x * 2 + 1] + st[x * 2 + 2];
}



int sum1(int l, int r, int x, int lx, int rx){
    if (l >= rx || lx >= r){
        return 0;
    }
    if (lx >= l && rx <= r){
        return st[x];
    }
    m = (lx + rx) / 2;
    return sum1(l, r, x * 2 + 1, lx, m) + sum1(l, r, x * 2 + 2, m, rx);
}

int k_(int k, int x, int lx, int rx){
    if (rx - lx == 1){
        return lx;
    }
    m = (lx + rx) / 2;
    if (st[x * 2 + 1] <= k){
        return k_(k - st[x * 2 + 1], x * 2 + 2, m, rx);
    }
    return k_(k, x * 2 + 1, lx, m);
}


int main() {
    cin >> n;
    for (int _; _ < n; _++){
        cin >> i >> x;
        if (i == 1){
            z += 1;
            cout << sum1(x, 100'005, 0, 0, 100'005) << '\n';
            set1(x, 1, 0, 0, 100'005);
        }
        else {
            z -= 1;
            i = k_(z - x, 0, 0, 100'005);
            set1(i, 0, 0, 0, 100'005);
        }
    }
}

БЛОГ НА HUSL

Построение acmp

Ответы (2 шт):