[정올] 1506 / 안전한 철판

// Preset 생략

int power, cnt;

struct Line
{
    int ymin;
    int ymax;
    int x;
    int idx;
};

vector<Line> lines;
vector<int> ables[1005];

bool ables_[1005];
bool execpt[1005];

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> power >> cnt;

    int yrmin = 1000;
    int yrmax = 0;

    for (int i = 0; i < cnt; i++)
    {
        int idx, xn, ymin, ymax;
        cin >> idx >> xn >> ymin >> ymax;
        yrmin = min(yrmin, ymin);
        yrmax = max(yrmax, ymax);
        lines.push_back({ymin,
                         ymax,
                         xn,
                         idx});
    }

    sort(
        lines.begin(), lines.end(), [](const Line &a, const Line &b)
        { return a.x < b.x; });

    for (auto l : lines)
    {
        for (int j = l.ymin; j < l.ymax; j++)
        {
            ables[j].push_back(l.idx);
        }
    }

    for (int oo = yrmin; oo < yrmax; oo++)
    {
        if (ables[oo].size() <= power)
        {
            for (int yy = 0; yy < ables[oo].size(); yy++)
            {
                execpt[ables[oo][yy]] = 1;
            }
            continue;
        }
        for (int yy = 0; yy < power; yy++)
        {
            execpt[ables[oo][yy]] = 1;
        }
        for (int yy = power; yy < ables[oo].size(); yy++)
        {
            ables_[ables[oo][yy]] = 1;
        }
    }

    bool n = 0;
    for (int i = 1; i <= cnt; i++)
    {
        if (!ables_[i] || execpt[i])
            continue;

        cout << i << " ";
        n = 1;
    }

    if (!n)
        cout << "0";
}