Submission #1162878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162878		DangKhoizzzz	RMQ (NOI17_rmq)	C++17	100 / 100	37 ms	10432 KiB

rmq

#include <bits/stdc++.h>
#include <cstdlib>
#define ll long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e9 + 7;
const int maxn = 1e5 + 7;

int n , q , ans[maxn];
arr3 query[maxn];
vector <pii> num[maxn];

bool check = 1;

void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> query[i][0] >> query[i][1] >> query[i][2];
        query[i][0]++; query[i][1]++; query[i][2]++;
        num[query[i][2]].push_back({query[i][0] , query[i][1]});
    }
    set <int> index; // unused
    vector <int> uu;
    for(int i = 1; i <= n; i++)
    {
        uu.push_back(i);
        index.insert(i);
    }

    index.insert(n+1);

    vector <int> val;

    for(int i = n; i >= 1; i--)
    {
        if(num[i].empty()) continue;

        int limL = 0 , limR = n+1;

        vector <int> pos;

        while(!uu.empty() && uu.back() >= i)
        {
            val.push_back(uu.back());
            uu.pop_back();
        }

        for(pii tmp: num[i])
        {
            int cur = *index.lower_bound(tmp.fi);
            limL = max(limL , tmp.fi);
            limR = min(limR , tmp.se);
            while(cur <= tmp.se)
            {
                pos.push_back(cur);
                index.erase(cur);
                cur = *index.upper_bound(cur);
            }
        }

        sort(pos.begin() , pos.end());

        if(pos.empty())
        {
            check = false; break;
        }

        int pp = *lower_bound(pos.begin() , pos.end() , limL);

        if(limL > limR ||pp > limR || pos.size() > val.size())
        {
            check = false; break;
        }

        ans[pp] = i;
        val.pop_back();

        for(int p: pos)
        {
            if(p == pp) continue;
            ans[p] = val.back();
            val.pop_back();
        }
    }

    for(int i = 1; i <= n; i++)
    {
        if(ans[i] == 0 && !uu.empty())
        {
            ans[i] = uu.back();
            uu.pop_back();
        }
        else if(ans[i] == 0 && !val.empty())
        {
            ans[i] = val.back();
            val.pop_back();
        }
    }

    if(!check)
    {
        for(int i = 1; i <= n; i++) cout << -1 << ' ';
        return;
    }
    for(int i = 1; i <= n; i++) cout << --ans[i] << ' ';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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