Submission #1249028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249028		vicvic	RMQ (NOI17_rmq)	C++20	100 / 100	51 ms	11440 KiB

rmq

#include <bits/stdc++.h>

using namespace std;
const int NMAX=2e5;
int n, q, l[NMAX+5], r[NMAX+5], l2[NMAX+5], r2[NMAX+5], ans[NMAX+5];
void blud ()
{
    for (int i=0;i<n;i++)
    {
        cout << "-1 ";
    }
    exit (0);
}
int main ()
{
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> q;
    for (int i=0;i<n;i++)
        r2[i]=l[i]=-1, l2[i]=r[i]=1e9;
    while (q--)
    {
        int x, y, val;
        cin >> x >> y >> val;
        l[val]=max (l[val], x);
        r[val]=min (r[val], y);
        l2[val]=min (l2[val], x);
        r2[val]=max (r2[val], y);
    }
    set <int> pos, cows;
    for (int i=0;i<n;i++)
        pos.insert (i), cows.insert (i);
    for (int i=n-1;i>=0;i--)
    {
        if (l[i]==-1)
            continue;
        auto itr=pos.lower_bound (l[i]);
        if (itr==pos.end() || (*itr)>r[i])
            blud ();
        ans[*itr]=i;
        pos.erase (*itr);
        cows.erase (i);
        while (pos.size())
        {
            auto itr=pos.lower_bound (l2[i]);
            if (itr==pos.end() || (*itr)>r2[i])
                break;
            int x=*cows.rbegin();
            if (x<i)
                blud ();
            ans[*itr]=x;
            pos.erase (itr);
            cows.erase (x);
        }
    }
    while (pos.size())
    {
        ans[*pos.begin()]=*cows.begin();
        pos.erase (pos.begin());
        cows.erase (cows.begin());
    }
    for (int i=0;i<n;i++)
        cout << ans[i] << " ";
    return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 44 / 44
• Subtask 3: 33 / 33