Submission #499121

#	Time	Username	Problem	Language	Result	Execution time	Memory
499121		blue	RMQ (NOI17_rmq)	C++17	30 / 100	88 ms	18292 KiB

rmq

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

const int lg = 16;
const int mx = 100'000;

using vi = vector<int>;

int st[mx][1+lg];
vi maxpow(1+mx);

int rangemin(int l, int r)
{
    return min(st[l][maxpow[r-l+1]], st[r - (1 << maxpow[r-l+1]) + 1][maxpow[r-l+1]]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    maxpow[1] = 0;
    for(int i = 2; i <= mx; i++)
    {
        maxpow[i] = maxpow[i-1];
        if((1 << (maxpow[i]+1)) == i)
            maxpow[i]++;
    }

    int N, Q;
    cin >> N >> Q;

    vi le[N], re[N];

    int L[Q], R[Q], A[Q];
    for(int j = 0; j < Q; j++)
    {
        cin >> L[j] >> R[j] >> A[j];
        le[L[j]].push_back(j);
        re[R[j]].push_back(j);
    }

    multiset<int> V{0};

    vi P(N);

    for(int i = 0; i < N; i++)
    {
        for(int j: le[i])
            V.insert(A[j]);

        P[i] = *V.rbegin();

        // cerr << i << " : ";
        // for(int v: V) cerr << v << ' ';
        // cerr << '\n';
        //
        // cerr << "P[i] = " << P[i] << '\n';

        for(int j: re[i])
            V.erase(V.find(A[j]));
    }

    for(int i = 0; i < N; i++)
        st[i][0] = P[i];

    for(int e = 1; e <= lg; e++)
        for(int i = 0; i+(1<<e)-1 < N; i++)
            st[i][e] = min(st[i][e-1], st[i + (1 << (e-1))][e-1]);

    for(int j = 0; j < Q; j++)
    {
        if(rangemin(L[j], R[j]) != A[j])
        {
            for(int i = 0; i < N; i++) cout << "-1 ";
            cout << '\n';
            return 0;
        }
    }

    for(int i = 0; i < N; i++) cout << P[i] << ' ';
    cout << '\n';
}

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