Блокировки

[inky]

Кажется, я немного облажался с сортировкой.. сейчас исправлю

[Geen]

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

Исправил

Ну два условия в if, а не 4!....

[12d3]

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

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

Согласен. В худшем случае, у нас всем равно будут в структуре сидеть все блокировки, и тогда удаление старых - это лишняя операция (но худший случай для неудаления старых и худший случай для удаления старых - это разные худшие случаи). А вот что будет выгоднее в среднем - пока не знаю. С одной стороны, если не удалять просроченные, это минус одна операция, с другой стороны, если удалять просроченные, у нас будет меньше элементов в структуре, что определенно плюс.

[Geen]

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

у нас будет меньше элементов в структуре, что определенно плюс.

Если поиск логарифмичен это не очень критично...

[12d3]

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

Если поиск логарифмичен это не очень критично...

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

[inky]

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

Ну два условия в if, а не 4!....

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

if (!(it->end < start) &&
    !(it->start > end)) {
    cout << "No";
    return 1;
}
 

-- 16.06.2017, 16:54 --

Не могу понять, где я теперь накосячил....неверный ответ на 7-ом тесте. Видимо, какие-то активные блокировки остаются в хвосте. Функция insert вроде как добавляет элемент перед итератором.

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

#include <iostream>
#include <list>

using namespace std;

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

int block_me(list<block> *blocked, int time, int start, int end, int duration) {
    list<block>::const_iterator spot = blocked->cbegin();
    
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (it->time <= time) {
            break;
        }
        if (it->time > spot->time) {
            spot = it;
            ++spot;
        }
        
        if (!(it->end < start) &&
            !(it->start > end)) {
            cout << "No";
            return 1;
        }
    }
    
    block t = {
        .start = start,
        .end = end,
        .time = time + duration
    };
    blocked->insert(spot, 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;
}
 

-- 16.06.2017, 17:13 --

Все, понял где облажался. И исправил.

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

#include <iostream>
#include <list>

using namespace std;

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

int block_me(list<block> *blocked, int time, int start, int end, int duration) {
    list<block>::const_iterator spot = blocked->cbegin();
    
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (it->time <= time) {
            break;
        }
        if (it->time > time + duration) {
            spot = it;
            ++spot;
        }
        
        if (!(it->end < start) &&
            !(it->start > end)) {
            cout << "No";
            return 1;
        }
    }
    
    block t = {
        .start = start,
        .end = end,
        .time = time + duration
    };
    blocked->insert(spot, 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;
}
 

-- 16.06.2017, 17:37 --

Снова застрял..не проходит ограничение по времени на 17-ом тесте

[rockclimber]

На каких языках там можно писать? Java или паскаль в списке доступных есть? Тоже что ли попробую

[inky]

rockclimber
Можно. Вот ссылка. Задача E.

[rockclimber]

inky
"У вас нет прав просматривать это соревнование"
Надо предварительно другие задания пройти?

[inky]

rockclimber
Это были задачки на стажировку, регистрация на которую уже закрыта.

-- 16.06.2017, 18:54 --

Я не смог решить эту задачу с блокировками и теперь она не дает мне покоя

-- 16.06.2017, 19:07 --

Geen, 12d3 я попробовал реализовать через set. Но, похоже, что-то не учел, программа выдает неверный ответ на 9-ом тесте..
Почитал документацию к set, переписал оператор "<" так, чтобы для неподходящей блокировки

!comp(a, b) && !comp(b, a) == true

.

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

#include <iostream>
#include <set>

using namespace std;

class Block {
    int start, end, time, duration, expires;
    
public:
    Block(int time, int start, int end, int duration) : start(start), end(end), time(time), duration(duration), expires(time + duration) {}
    
    Block() {}
    
    Block& operator=(const Block& r) {
        this->time = r.time;
        this->start = r.start;
        this->end = r.end;
        this->duration = r.duration;
        this->expires = r.expires;
        return *this;
    }
    
    bool operator<(const Block& r) const {
        Block first, second;
        if (this->time < r.time) {
            first = *this;
            second = r;
        } else {
            first = r;
            second = *this;
        }
        
        if (first.expires > second.time &&
            !(first.end < second.start) &&
            !(first.start > second.end)) {
            return false;
        }
        
        return first.time < second.time;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    set<Block> blocked;
    for (int i = 0; i < m; ++i) {
        int s, l, r, d;
        cin >> s >> l >> r >> d;
        Block t(s, l, r, d);
        auto res = blocked.insert(t);
        if (res.second) {
            cout << "Yes";
        } else {
            cout << "No";
        }
        cout << endl;
    }

    return 0;
}
 

[12d3]

inky
Так можно сортировать просто по левой границе занимаемых ресурсов, т.е. по возрастанию start. И будем следить, чтобы у блокировок, которые находятся в множестве, промежутки $[start;end]$ не пересекались. Делаем примерно так:
На этапе проверки на пересечение с имеющимимся блокировками, ищем наименьший элемент, у которого start больше вставляемого, а также наибольший элемент, у которого start меньше вставляемого. Если эти товарищи пересекаются (как прямоугольники), то не вставляем. А если не пересекаются прямоугольники, но пересекаются "в проекции" на ось ресурсов, то удаляем старый(е) и вставляем новый. А если даже в проекции не пересекаются, то просто вставляем.
UPD. Конечно же, проверять на пересечение надо не только найденные в множестве наибольший и наименьший, но и все между ними.

[Geen]

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

попробовал реализовать через set.

Просто set не поможет (на множестве отрезков у нас не полное упорядочивание).
Возможно надо самому реализовать какое-нибудь достаточно сбалансированное дерево с эффективным блочным удалением...
Только всю память надо выделять один раз в начале.

[inky]

12d3
Чуть позже попробую реализовать.

Geen
Я надеюсь, что не придется самому писать дерево

[Geen]

Кстати, а сколько бит там int?

[inky]

Geen
Не меньше 16 бит. На 64-разрядных обычно 32 бита.

-- 16.06.2017, 20:50 --

12d3
Реализовал, но определенно где-то закралась ошибка: runtime error на седьмом тесте.

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

#include <iostream>
#include <set>

using namespace std;

class Block {
    int start, end, time, duration, expires;
    
public:
    Block(int time, int start, int end, int duration) : start(start), end(end), time(time), duration(duration), expires(time + duration) {}
    
    Block() {}
    
    Block& operator=(const Block& r) {
        this->time = r.time;
        this->start = r.start;
        this->end = r.end;
        this->duration = r.duration;
        this->expires = r.expires;
        return *this;
    }
    
    bool operator<(const Block& r) const {
        return this->start < r.start;
    }
    
    bool intersects(Block bl) const {
        if (!(this->end < bl.start) &&
            !(this->start > bl.end) &&
            ((this->time < bl.time && this->expires > bl.time) ||
             (bl.time < this->time && bl.expires > this->time))) {
            return true;
        }
        return false;
    }
    
    bool resources_intersect(Block bl) const {
        if (!(this->end < bl.start) &&
            !(this->start > bl.end)) {
            return true;
        }
        return false;
    }
};

bool insert(set<Block> *blocked, Block bl) {
    set<Block>::iterator up = blocked->upper_bound(bl), low;
    if (up != blocked->end() || !blocked->empty()) {
        low = prev(up);
    } else {
        low = up;
    }
    
    if ((low != blocked->end() && low->intersects(bl)) ||
        (up != blocked->end() && up->intersects(bl))) {
        return false;
    }
    
    if (low != blocked->end() && low->resources_intersect(bl)) {
        blocked->erase(low);
    }
    
    if (up != blocked->end() && up->resources_intersect(bl)) {
        blocked->erase(up);
    }
    
    blocked->insert(bl);
    
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    set<Block> blocked;
    for (int i = 0; i < m; ++i) {
        int s, l, r, d;
        cin >> s >> l >> r >> d;
        Block t(s, l, r, d);
        if (insert(&blocked, t)) {
            cout << "Yes";
        } else {
            cout << "No";
        }
        cout << endl;
    }
    
    return 0;
}