oj.uz

Submission #738154

# Submission time Handle Problem Language Result Execution time Memory
738154 2023-05-08T08:21:38 Z Ronin13 RMQ (NOI17_rmq) C++14
100 / 100
 150 ms 16168 KB 
#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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9676 KB Output is correct
9 Correct 5 ms 9744 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct

Subtask #2
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9676 KB Output is correct
9 Correct 5 ms 9744 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 5 ms 9732 KB Output is correct
13 Correct 7 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 7 ms 9684 KB Output is correct
16 Correct 6 ms 9740 KB Output is correct
17 Correct 6 ms 9684 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 5 ms 9736 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 5 ms 9700 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct
25 Correct 5 ms 9684 KB Output is correct
26 Correct 5 ms 9684 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9676 KB Output is correct
9 Correct 5 ms 9744 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 4 ms 9684 KB Output is correct
12 Correct 5 ms 9732 KB Output is correct
13 Correct 7 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 7 ms 9684 KB Output is correct
16 Correct 6 ms 9740 KB Output is correct
17 Correct 6 ms 9684 KB Output is correct
18 Correct 5 ms 9684 KB Output is correct
19 Correct 5 ms 9684 KB Output is correct
20 Correct 5 ms 9736 KB Output is correct
21 Correct 5 ms 9684 KB Output is correct
22 Correct 6 ms 9684 KB Output is correct
23 Correct 5 ms 9700 KB Output is correct
24 Correct 6 ms 9684 KB Output is correct
25 Correct 5 ms 9684 KB Output is correct
26 Correct 5 ms 9684 KB Output is correct
27 Correct 131 ms 15384 KB Output is correct
28 Correct 121 ms 15816 KB Output is correct
29 Correct 100 ms 15456 KB Output is correct
30 Correct 150 ms 16168 KB Output is correct
31 Correct 99 ms 14664 KB Output is correct
32 Correct 110 ms 14668 KB Output is correct
33 Correct 52 ms 14924 KB Output is correct
34 Correct 39 ms 13220 KB Output is correct
35 Correct 67 ms 15800 KB Output is correct
36 Correct 94 ms 14392 KB Output is correct
37 Correct 111 ms 13960 KB Output is correct
38 Correct 40 ms 13808 KB Output is correct
39 Correct 118 ms 15736 KB Output is correct
40 Correct 5 ms 9724 KB Output is correct
41 Correct 4 ms 9684 KB Output is correct