Submission #738154

#	Time	Username	Problem	Language	Result	Execution time	Memory
738154		Ronin13	RMQ (NOI17_rmq)	C++14	100 / 100	150 ms	16168 KiB

rmq

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
const int nmax = 200001;
vector <int> lazy(4 * nmax);
vector <pii> t(4 * nmax);

void push(int v){
    lazy[2 * v] = max(lazy[2 * v], lazy[v]);
    t[v * 2].f = max(t[v * 2].f, lazy[v]);
    lazy[2 * v + 1] = max(lazy[2 * v + 1], lazy[v]);
    t[v * 2 + 1].f = max(t[2 * v  + 1].f, lazy[v]);
}


void upd(int v, int l, int r, int st, int fin, int val){
    if(l > fin || r < st)
        return;
    if(l >= st && r <= fin){
        lazy[v] = max(lazy[v], val);
        t[v].f = max(t[v].f, val);
        return;
    }
    int m = (l + r) / 2;
    push(v);
    upd(2 * v, l, m, st, fin, val);
    upd(2 * v + 1, m + 1, r, st, fin, val);
    t[v] = min(t[2 * v], t[2 * v + 1]);
}

pii get(int v, int l, int r, int st, int fin){
    if(l > fin || r < st)
        return {1e9, 1e9};
    if(l >= st && r <= fin){
        return t[v];
    }
    push(v);
    int m= (l + r) / 2;
    return min(get(2 * v, l, m, st, fin), get(2 * v + 1, m + 1, r, st, fin));
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int q; cin >> q;
    int l[n], r[n];
    fill(l, l + n, -1);
    fill(r, r + n, n);
    for(int i = 1; i <= q; i++){
        int L, R, v; cin >> L >> R >> v;
        l[v] = max(l[v], L);
        r[v] = min(r[v], R);
        upd(1, 0, n - 1, L, R, v);
    }
    bool good = true;
    set <int> unused;
    for(int i = 0; i < n; ++i){
        if(l[i] > r[i]) good = false;

        if(l[i] < 0) unused.insert(i);
    }
    vector <bool> used(n);
    vector <int> ans(n);
    for(int i= 0; i < n; i++){
        pii x = get(1, 0, n - 1, i, i);
       // cout << x.f << ' ';
        if(used[x.f] || l[x.f] > i || r[x.f] < i){
            auto it = unused.upper_bound(x.f);
            if(it == unused.end()) good = false;
            else ans[i] = *it, unused.erase(it);
        }
        else used[x.f] = true, ans[i] = x.f;
    }
    if(!good){
        for(int i = 0; i < n; i++)
            cout << -1 << ' ';
        cout << "\n";
    }
    else{
        for(int i = 0; i < n; i++){
            cout << ans[i] << ' ';
        }
    }
}

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