Блокировки

[inky]

Есть $n$ абстрактных ресурсов, пронумерованные целыми числами от $1$ до $n$. Каждый ресурс в конкретный момент времени может находиться либо в занятом, либо в свободном состоянии. Изначально (в момент времени $0$) все ресурсы находятся в свободном состоянии.
Блокировка с порядковым номером $i$ представляет из себя четверку чисел ($s_i, l_i, r_i, d_i$), обозначающих соответственно время старта ($s_i \geqslant 1$), левую и правую границы индексов ресурсов ($1 \leqslant l_i \leqslant r_i \leqslant n$), продолжительность ($d_i \geqslant 1$) блокировки.
Блокировка $i$ называется принятой, если на момент времени $s_i$ все ресурсы с индексами в диапазоне $[l_i, r_i]$ находятся в свободном состоянии. Принятая блокировка $i$ переводит все ресурсы с индексами в диапазоне $[l_i, r_i]$ в занятое состояние для всех моментов времени в диапазоне $[s_i, s_i + d_i)$.
Необходимо реализовать алгоритм, реализующий данную логику.

Формат входных данных
В первой строке входных данных записано два числа — $n, m$ $(1 \leqslant n, m \leqslant 100000)$, разделенных одним пробелом.
В последующих $m$ строках задано описание блокировок в примере Васи. В $i$-й из этих строк записано четыре числа — $s_i, l_i, r_i, d_i$ $(1 \leqslant s_i \leqslant 10^9, 1 \leqslant l_i \leqslant r_i \leqslant 10^9, 1 \leqslant d_i \leqslant 10^9)$, разделенных одним пробелом.
Гарантируется, что все $s_i$ различны.Блокировки следуют в порядке возрастания величины $s_i$.

Формат выходных данных
В $i$-й строке выходных данных необходимо вывести результат обработки $i$-й блокировки в порядке следования во входных данных: если $i$-я блокировка является принятой, вывести Yes, иначе No.


Мое решение:

#include <iostream>
#include <vector>

using namespace std;

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

int clear (int time, vector<block> *blocked) { // clear outdated blocks
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (it->time <= time) {
            blocked->erase(it);
            return 1;
        }
    }
    return 0;
}

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;
}

int block_me(vector<block> *blocked, int time, int start, int end, int duration) {
    while (clear(time, blocked) == 1);
    
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (intersects(it, start, end) == 1) {
            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;
    vector<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;
}

Решение проверяется системой yandex contest. На седьмом тесте мой код выдает неверный ответ. Никак не могу понять, что я упустил?

[rockclimber]

Я вряд ли помогу вам именно с С/С++, но из общих соображений:
1. На каких входных данных вы тестировали код?
2.

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

На седьмом тесте мой код выдает неверный ответ.

Как мне кажется, было бы неплохо уточнить, что такое "седьмой тест".

[inky]

rockclimber
Седьмой тест -- это седьмой тест автоматической системы тестирования яндекса. К сожалению, у меня нет доступа к этим тестам

-- 16.06.2017, 13:15 --

У меня был еще другой вариант решения, но он на 19-ом тесте слишком долго работал, не прошел ограничение по времени.
Вот он:

#include <iostream>

using namespace std;

int block_me(int *a, int time, int start, int end, int duration) {
    for (int i = start; i <= end; ++i) {
        if (a[i] > time) {
            printf("No");
            for (int j = start; j < i; ++j) {
                a[j] = time;
            }
            return 1;
        }
        a[i] = time + duration;
    }
    printf("Yes");
    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    int resources[n];
    for (int i = 0; i < n; ++i) {
        resources[i] = 0;
    }
    for (int i = 0; i < m; ++i) {
        int s, l, r, d;
        cin >> s >> l >> r >> d;
        block_me(resources, s, l - 1, r - 1, d);
        printf("\n");
    }
    
    return 0;
}

[Geen]

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

Никак не могу понять, что я упустил?

А перекрытие блоков как считается?

[inky]

Geen
Перекрытие я учитываю в этой функции:

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;
}

[Geen]

rockclimber в сообщении #1226007 писал(а):

Как мне кажется, было бы неплохо уточнить, что такое "седьмой тест".

Я думаю, что это просто очередной набор данных для тестирования.

-- 16.06.2017, 11:25 --

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

Перекрытие я учитываю в этой функции:

Так я спрашивал "как"

[inky]

Geen
Вначале понял это как "пересечение". Я лишь смотрел на пересечения. Если новая блокировка пересекается с одной из активных блокировок -- значит блокировку надо отменять.

-- 16.06.2017, 13:31 --

А учитываю я их так: если начало либо конец новой блокировки лежит внутри активной блокировки, то они пересекаются.

[Geen]

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

А учитываю я их так: если начало либо конец новой блокировки лежит внутри активной блокировки, то они пересекаются.

Лучше бы зайти с другого конца - когда блокировки не пересекаются?

[rockclimber]

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

[inky]

rockclimber в сообщении #1226040 писал(а):

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

Время я специально отсекаю в функции $clear$. Чтобы не мучиться с двумя измерениями

-- 16.06.2017, 13:40 --

Geen
Сейчас попробую.

-- 16.06.2017, 13:45 --

Geen
Спасибо, работало
Поменял функцию $intersects$:

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

Видимо, старая неверно считала пересечение

Но теперь я не укладываюсь по времени на 17-ом тесте...

[rockclimber]

Меня вот что смущает:

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

Гарантируется, что все $s_i$ различны. Блокировки следуют в порядке возрастания величины $s_i$.

Но не гарантируется, что $s_{i+1} > s_i + d_i$
Может, в этом проблема?

[inky]

rockclimber в сообщении #1226048 писал(а):

Но не гарантируется, что $s_{i+1} > s_i + d_i$
Может, в этом проблема?

Нет, тут все в порядке. Если $s_{i} < s_k + d_k$, то надо блокировка считается непринятой.

[Geen]

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

У меня был еще другой вариант решения, но он на 19-ом тесте слишком долго работал, не прошел ограничение по времени.

Похоже в яндексе знают толк в извращениях
Но Ваш текущий вариант мне как-то тоже не сильно нравится - слишком много удалений из начала массива (вектора) может случиться...

-- 16.06.2017, 11:52 --

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

Но теперь я не укладываюсь по времени на 17-ом тесте...

Видимо оно и случилось...

-- 16.06.2017, 11:53 --

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

Поменял функцию $intersects$:

Избыточные условия....

[inky]

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

Но Ваш текущий вариант мне как-то тоже не сильно нравится - слишком много удалений из начала массива (вектора) может случиться...

Только что попробовал перенести эти удаления поближе - в саму функцию block_me:

#include <iostream>
#include <vector>

using namespace std;

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

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

int block_me(vector<block> *blocked, int time, int start, int end, int duration) {
    for (auto it = blocked->cbegin(); it != blocked->cend(); ++it) {
        if (it->time <= time) {
            blocked->erase(it);
            return block_me(blocked, time, start, end, duration);
        }
        if (intersects(it, start, end) == 1) {
            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;
    vector<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;
}

Но толку не было. Совсем :)

[rockclimber]

А можете вкратце словами описать алгоритм? Я не уверен, что правильно понял код. И, как я понимаю, у вас остались только проблемы с производительностью?