Блокировки

[Geen]

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

Не меньше 16 бит.

Мало... И для $10^5$, и тем более для $10^9$...

[12d3]

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

Реализовал, но определенно где-то закралась ошибка

Я чуть позже добавил в свой пост.

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

UPD. Конечно же, проверять на пересечение надо не только найденные в множестве наибольший и наименьший, но и все между ними.

[quartermind]

Есть специальная структура данных для работы с отрезками — дерево отрезков. Эта задача как раз про неё.

[inky]

quartermind
Спасибо, чуть позже почитаю.

12d3
Наверное, буду исправлять уже завтра. Надеюсь, сработает.

-- 16.06.2017, 21:13 --

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

Мало... И для $10^5$, и тем более для $10^9$...

Действительно Исправил везде на long int.

[Geen]

quartermind в сообщении #1226280 писал(а):

Есть специальная структура данных для работы с отрезками — дерево отрезков. Эта задача как раз про неё.

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

-- 16.06.2017, 23:55 --

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

Спасибо, чуть позже почитаю.

Лучше пока не читайте...

[inky]

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

Лучше пока не читайте...

Почитал, но вникнуть времени не было

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

Кстати, а к тестовым наборам у Вас, случайно, нет доступа?

К сожалению нет.

-- 17.06.2017, 17:55 --

12d3
Реализовал, но падает на седьмом тесте Неверный ответ выдает.

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

#include <iostream>
#include <set>
#include <vector>

using namespace std;

class Block {
    long int rstart, rend, tstart, tend;
    
public:
    Block(long int time, long int start, long int end, long int duration) : rstart(start), rend(end), tstart(time), tend(time + duration - 1) {}
    
    Block() {}
    
    Block& operator=(const Block& rhs) {
        this->rstart = rhs.rstart;
        this->rend = rhs.rend;
        
        this->tstart = rhs.tstart;
        this->tend = rhs.tend;
        
        return *this;
    }
    
    bool operator<(const Block& rhs) const {
        return this->rstart < rhs.rstart;
    }
    
    friend ostream &operator<<(ostream &output, const Block &bl) {
        output << bl.tstart << " " << bl.rstart << " " << bl.rend << " " << bl.tend - bl.tstart + 1;
        return output;
    }
    
    bool resource_intersect(Block bl) const {
        return !(this->rstart > bl.rend || this->rend < bl.rstart);
    }
    
    bool time_intersect(Block bl) const {
        return !(this->tstart > bl.tend || this->tend < bl.tstart);
    }
};

set<Block>::iterator get_next(set<Block>::iterator it, set<Block> *blocked) {
    if (it == blocked->end()) {
        return it;
    }
    return next(it);
}

set<Block>::iterator get_prev(set<Block>::iterator it, set<Block> *blocked) {
    if (it == blocked->begin()) {
        return blocked->end();
    }
    return prev(it);
}

bool range_intersect(set<Block>::iterator low, set<Block>::iterator high, Block bl, set<Block> *blocked) {
    for (auto it = low; it != get_next(high, blocked); ++it) {
        if (it->time_intersect(bl) && it->resource_intersect(bl)) {
            return true;
        }
    }
    return false;
}

void clear_resource_range(set<Block>::iterator low, set<Block>::iterator high, Block bl, set<Block> *blocked) {
    vector<set<Block>::iterator> clear_me;
    for (auto it = low; it != get_next(high, blocked); ++it) {
        if (it->resource_intersect(bl)) {
            clear_me.push_back(it);
        }
    }
    
    for (auto it = clear_me.rbegin(); it != clear_me.rend(); ++it) {
        blocked->erase(*it);
    }
}

bool insert(set<Block> *blocked, Block bl) {
    if (!blocked->empty()) {
        set<Block>::iterator high = blocked->lower_bound(bl), low;
        
        if (high == blocked->end()) {
            --high;
        }
        
        low = high;
        for (auto it = high; it != blocked->end(); it = get_prev(it, blocked)) {
            if (*it < bl) {
                low = it;
                break;
            }
        }
        
        for (auto it = high; it != blocked->end(); it = get_next(it, blocked)) {
            if (bl < *it) {
                high = it;
                break;
            }
        }
        
        if (range_intersect(low, high, bl, blocked)) {
            return false;
        }
        
        clear_resource_range(low, high, bl, blocked);
    }
    
    blocked->insert(bl);
    
    return true;
}

int main() {
    long int n, m;
    cin >> n >> m;
    set<Block> blocked;
    
    for (long int i = 0; i < m; ++i) {
        long 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;
}
 

-- 17.06.2017, 18:10 --

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

На этапе проверки на пересечение с имеющимимся блокировками, ищем наименьший элемент, у которого start больше вставляемого, а также наибольший элемент, у которого start меньше вставляемого.

Кажется, я понял в чем дело. Для high надо искать тот элемент, у которого resource_start больше, чем resource_end вставляемого, а для low нужен наибольший элемент, у которого resource_start меньше, чем resource_start вставляемого. Сейчас попробую реализовать

-- 17.06.2017, 18:18 --

Поменял

for (auto it = high; it != blocked->end(); it = get_next(it, blocked)) {
    if (bl < *it) {
        high = it;
        break;
    }
}

на

for (auto it = high; it != blocked->end(); it = get_next(it, blocked)) {
    if (!bl.resource_intersect(*it)) {
        high = it;
        break;
    }
}

Не помогло, все равно неверный ответ на 7 тесте...

-- 17.06.2017, 18:38 --

Убрал функцию clear_resource_range, поменял функцию range_intersect на

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

void erase(set<Block> *blocked, vector<set<Block>::iterator> items) {
    for (auto it = items.rbegin(); it != items.rend(); ++it) {
        blocked->erase(*it);
    }
}

bool range_intersect(set<Block>::iterator low, set<Block>::iterator high, Block bl, set<Block> *blocked) {
    vector<set<Block>::iterator> erase_us;
    for (auto it = low; it != get_next(high, blocked); ++it) {
        if (!it->time_intersect(bl)) {
            erase_us.push_back(it);
        } else if (it->resource_intersect(bl)) {
            erase(blocked, erase_us);
            return true;
        }
    }
    erase(blocked, erase_us);
    return false;
}
 

и мой код уже падает на 9-ом тесте
Похоже, раньше он удалял какие-то активные блокировки...да и сейчас тоже...

[inky]

Ура! Наконец-то дорешал Успешно прошел все 25 тестов:

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

#include <iostream>
#include <set>
#include <vector>

using namespace std;

class Block {
    long int rstart, rend, tstart, tend;
    
public:
    Block(long int time, long int start, long int end, long int duration) : rstart(start), rend(end), tstart(time), tend(time + duration - 1) {}
    
    Block() {}
    
    Block& operator=(const Block& rhs) {
        this->rstart = rhs.rstart;
        this->rend = rhs.rend;
        
        this->tstart = rhs.tstart;
        this->tend = rhs.tend;
        
        return *this;
    }
    
    bool operator<(const Block& rhs) const {
        return this->rstart < rhs.rstart;
    }
    
    friend ostream &operator<<(ostream &output, const Block &bl) {
        output << bl.tstart << " " << bl.rstart << " " << bl.rend << " " << bl.tend - bl.tstart + 1;
        return output;
    }
    
    bool resource_intersect(Block bl) const {
        return !(this->rstart > bl.rend || this->rend < bl.rstart);
    }
    
    bool time_intersect(Block bl) const {
        return !(this->tstart > bl.tend || this->tend < bl.tstart);
    }
};

set<Block>::iterator get_next(set<Block>::iterator it, set<Block> *blocked) {
    if (it == blocked->end()) {
        return it;
    }
    return next(it);
}

set<Block>::iterator get_prev(set<Block>::iterator it, set<Block> *blocked) {
    if (it == blocked->begin()) {
        return blocked->end();
    }
    return prev(it);
}

void erase(set<Block> *blocked, vector<set<Block>::iterator> items) {
    for (auto it = items.rbegin(); it != items.rend(); ++it) {
        blocked->erase(*it);
    }
}

bool range_intersect(set<Block>::iterator low, set<Block>::iterator high, Block bl, set<Block> *blocked) {
    vector<set<Block>::iterator> erase_us;
    for (auto it = low; it != get_next(high, blocked); ++it) {
        if (!it->time_intersect(bl)) {
            erase_us.push_back(it);
        } else if (it->resource_intersect(bl)) {
            erase(blocked, erase_us);
            return true;
        }
    }
    erase(blocked, erase_us);
    return false;
}

bool insert(set<Block> *blocked, Block bl) {
    if (!blocked->empty()) {
        set<Block>::iterator high = blocked->upper_bound(bl), low;
        
        if (high == blocked->end()) {
            --high;
        }
        
        for (auto it = high; it != blocked->end(); it = get_prev(it, blocked)) {
            low = it;
            if (*it < bl) {
                break;
            }
        }
        
        for (auto it = high; it != blocked->end(); it = get_next(it, blocked)) {
            high = it;
            if (!it->resource_intersect(bl)) {
                break;
            }
        }
        
        if (range_intersect(low, high, bl, blocked)) {
            return false;
        }
    }
    
    blocked->insert(bl);
    
    return true;
}

int main() {
    long int n, m;
    cin >> n >> m;
    set<Block> blocked;
    
    for (long int i = 0; i < m; ++i) {
        long 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;
}
 

-- 17.06.2017, 19:47 --

12d3
Моя ошибка была что я не учитывал, что при поиске low величина resource_start блокировок могут равняться. А при поиске high забыл учесть, что resource_end вставляемой блокировки может задеть resource_start блокировок, следующих после выбранного high.

Всем большое спасибо

-- 17.06.2017, 19:53 --

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

Ну нельзя же так сразу...

Теперь уже можно

[Geen]

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

Ура! Наконец-то дорешал Успешно прошел все 25 тестов

Поздравляю!

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

Теперь уже можно

Тогда надо и такой вариант попробовать