제출 #210009

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
210009		Alexa2001	RMQ (NOI17_rmq)	C++17	46.10 / 100	60 ms	8824 KiB

rmq

#include <bits/stdc++.h>
//#define no_sol { cout << "-1\n"; exit(0); }


using namespace std;

///11:12

const int Nmax = 1e5 + 5;

set<int> S;
int last, n, m;
vector<pair<int,int>> v[Nmax];
bool used[Nmax];
int ans[Nmax];



void no_sol()
{
    int i;
    for(i=0; i<n; ++i) cout << "-1 ";
    exit(0);
}



void add(int val, int start, int finish, int L, int R)
{
    set<int> :: iterator it = S.lower_bound(start), it2 = it;

    bool added = 0;

    while(it != S.end() && *it <= finish)
    {
        if(*it >= L && *it <= R && !added)
        {
            assert(used[val] == 0);
            ans[*it] = val;
            used[val] = 1;
            added = 1;
        }
        else
        {
            while(last>=0 && used[last]) --last;
            if(last <= val) no_sol();

            used[last] = 1;
            ans[*it] = last;
        }

        ++it;
    }

    if(!added) no_sol();
    S.erase(it2, it);
}

int main()
{
//    freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;

    int i;
    for(i=1; i<=m; ++i)
    {
        int x, y, val;
        cin >> x >> y >> val;
        v[val].push_back({x, y});
    }

    for(i=0; i<n; ++i) S.insert(i);

    last = n-1;

    for(i=n-1; i>=0; --i)
        if(v[i].size())
        {
            int lmin, rmax, lmax, rmin;
            lmin = rmin = n-1;
            lmax = rmax = 0;

            for(auto it : v[i])
            {
                int x, y;
                tie(x, y) = it;

                lmin = min(lmin, x);
                lmax = max(lmax, x);
                rmin = min(rmin, y);
                rmax = max(rmax, y);
            }

            if(lmax > rmin) no_sol();

            add(i, lmin, rmax, lmax, rmin);
        }

    for(auto it : S)
    {
        while(last>=0 && used[last]) --last;
        if(last < 0) no_sol();
        ans[it] = last;
    }


    for(i=0; i<n; ++i) cout << ans[i] << ' ';

    return 0;
}

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