Блокировки

[inky]

rockclimber
Если опустить скучные детали считывания данных, то:
У меня есть структура для блокировок, которая хранит диапазон заблокированных ресурсов и время, когда они освободятся.
Я создаю вектор из таких структур и каждую новую блокировку, если она принята, добавляю в вектор.
Процесс принятия/отклонения блокировки такой: я прохожусь по вектору блокировок и рассматриваю каждый элемент. Если блокировка уже неактивна, то удаляю ее, и перехожу к следующей. Если она активна, то смотрю, не пересекается ли она с новой блокировкой. Если пересекается, то вывожу No и выхожу из цикла, если не пересекается, то перехожу к следующей блокировке из вектора.
Если я так и не нашел активную блокировку, которая пересекается с новой блокировкой, то добавляю новую блокировку в вектор и печатаю Yes.

Появилась другая идея: попробую отсортировать массив по уменьшению времени и дойдя до неактивной блокировки буду отсекать хвост. Но уже вечером. Если сработает, напишу сюда. Спасибо за помощь Geen, rockclimber

[Geen]

inky в сообщении #1226067 писал(а):

Если блокировка уже неактивна, то удаляю ее, и перехожу к следующей.

Не совсем так - удаляю и начинаю поиск заново....

[inky]

Geen
Ааа, точно... спасибо, что заметили это.
Жаль, я уже выехал из дома. Чуть позже попробую это исправить.

[rockclimber]

А, еще хотел спросить. Не лучше ли этот код

int intersects(vector<block>::const_iterator it, int start, int end) {
    if ((start <= it->start && it->start <= end) ||
        (start <= it->end   && it->end   <= end)) {
        return 1;
    }
    return 0;
}

Записать как

Используется синтаксис C++

bool intersects(vector<block>::const_iterator it, int start, int end) {
    return (start <= it->start && it->start <= end) ||
           (start <= it->end   && it->end   <= end);
}

?
То есть оптимизатор может и сам оптимизирует, но лучше на всякий случай писать сразу нормально.

[inky]

rockclimber
Да, вы правы. Мой косяк

[Geen]

А ещё лучше инлайном и с правильным условием из двух сравнений

-- 16.06.2017, 12:26 --

inky в сообщении #1226067 писал(а):

попробую отсортировать массив по уменьшению времени

А по номерам ресурсов отсортировать тоже неплохо

[12d3]

Проблема в неправильном выборе структуры данных. У вас с массивом блокировок производятся следующие операции: итерирование, вставка в конец, удаление из середины. А доступ к произвольному элементу не используется. Значит, вам нужен не массив, а список.

[Geen]

12d3 в сообщении #1226076 писал(а):

Проблема в неправильном выборе структуры данных.

Согласен. И кроме того, судя по всему, тесты в яндексе это коллекция самых плохих случаев

12d3 в сообщении #1226076 писал(а):

Значит, вам нужен не массив, а список.

Я бы, всё же, что-нибудь отсортированное сделал для более быстрого поиска занятых блоков...

[rockclimber]

Geen в сообщении #1226091 писал(а):

Я бы, всё же, что-нибудь отсортированное сделал для более быстрого поиска занятых блоков...

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

[inky]

Geen в сообщении #1226075 писал(а):

А ещё лучше инлайном и с правильным условием из двух сравнений

Исправил Переписал таким образом:

Используется синтаксис C++

int block_me(vector<block> *blocked, int time, int start, int end, int duration, int istart) {
    for (int i = istart; i < blocked->size(); ++i) {
        if (blocked->at(i).time <= time) {
            blocked->erase(blocked->begin() + i);
            return block_me(blocked, time, start, end, duration, i);
        }
        if (!(blocked->at(i).start < start && blocked->at(i).end < start) &&
            !(blocked->at(i).start > end && blocked->at(i).end > end)) {
            cout << "No";
            return 1;
        }
    }
    block t = {
        .start = start,
        .end = end,
        .time = time + duration
    };
    blocked->push_back(t);
    cout << "Yes";
    return 0;
}
 

Правда, это не помогло. Все так же падает по времени на 17 тесте.

rockclimber, 12d3 Сейчас попробую переписать с отсортированным списком.

[12d3]

Хм. Попробую прикинуть, что выгоднее.
Итак, на каждой итерации у нас происходит следующее:
a) Удаление старых блокировок.
b) Проверка новой блокировки на пересечение с имеющимися.
c) Добавление новой.
И разные варианты:
1. Несортированный массив.
2. Сортированный массив.
3. Несортированный список.
4. Сортированное дерево, сиречь set.
$\begin{array}{|c|c|c|c|}\hline & a & b & c \\ \hline 1 & O(N) & O(N) & O(1) \\ \hline 2 & O(N) & O(log(N)) & O(N) \\ \hline 3 & O(N) & O(N) & O(1) \\ \hline 4 & O(log(N)) & O(log(N) & O(log(N)) \\ \hline \end{array}$
Так что я был неправ, нужен set. Список лучше несортированного массива, но совсем чуть-чуть.
P.S. Считаем что за одну итерацию в среднем удаляется одна блокировка.
UPD. Ошибся в временем удаления в списке. Все равно нам надо просматривать все элементы в списке, чтоб найти, кого удалить.

[inky]

rockclimber, 12d3, Geen
Использовал список, отсортировал его по убыванию времени -- если нахожу устаревшую блокировку, значит все последующие тоже неактивны, значит можно отрезать хвост. Но все равно падает по времени на 17-ом тесте..

Используется синтаксис C++

#include <iostream>
#include <list>

using namespace std;

struct block {
    int start, end, time;
};

bool compare_blocks (const block& first, const block& second) {
    return first.time >= second.time;
}

int block_me(list<block> *blocked, int time, int start, int end, int duration) {
    blocked->sort(compare_blocks);
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (it->time <= time) {
            blocked->erase(it, blocked->cend());
            break;
        }
        if (!(it->start < start && it->end < start) &&
            !(it->start > end && it->end > end)) {
            cout << "No";
            return 1;
        }
    }
    block t = {
        .start = start,
        .end = end,
        .time = time + duration
    };
    blocked->push_back(t);
    cout << "Yes";
    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    list<block> blocked;
    for (int i = 0; i < m; ++i) {
        int s, l, r, d;
        cin >> s >> l >> r >> d;
        block_me(&blocked, s, l, r, d);
        cout << endl;
    }
    
    return 0;
}
 

[Geen]

12d3 в сообщении #1226106 писал(а):

Удаление старых блокировок.

Необязательно. Нужно только если возникает пересечение с добавляемой.

[inky]

Geen в сообщении #1226112 писал(а):

Нужно только если возникает пересечение с добавляемой.

Я удаляю их, если пересечений не возникает

[Geen]

12d3 в сообщении #1226106 писал(а):

Сортированное дерево, сиречь set.

У нас два конца - можно попытаться использовать...