Submission #1171581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171581		hamzabc	RMQ (NOI17_rmq)	C++20	100 / 100	58 ms	53300 KiB

rmq

#include <bits/stdc++.h>

using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'


int N, Q;


class Tree{
public:
    vector<int> commoncontainer;

    struct dat{
        int say0 = 1;
        int l;
        int r;
        dat* lft;
        dat* rgt;
    };

    void copy(dat* root1, dat* root2){  // root2 = root1
        root2->l = root1->l;
        root2->r = root1->r;
        root2->lft = root1->lft;
        root2->rgt = root1->rgt;
        root2->say0 = root1->say0;
    }
private:
    void _init(dat* root, int l, int r){
        root->l = l;
        root->r = r;
        if (l == r)
            return;
        root->rgt = new dat;
        root->lft = new dat;
        int m = (l + r) >> 1;
        _init(root->lft, l, m);
        _init(root->rgt, m + 1, r);
        root->say0 = root->lft->say0 + root->rgt->say0;
    }

    void _update(int l, int r, dat* root){
        if (l <= root->l && root->r <= r){
            root->say0 = 0;
            return;
        }
        if (root->say0 == 0)
            return;
        if (root->lft->r >= l){
            dat* eski = root->lft;
            root->lft = new dat;
            copy(eski, root->lft);
            _update(l, r, root->lft);
        }
        if (root->rgt->l <= r){
            dat* eski = root->rgt;
            root->rgt = new dat;
            copy(eski, root->rgt);
            _update(l, r, root->rgt);
        }
        root->say0 = root->lft->say0 + root->rgt->say0;
    }

    int _first0(int l, int r, dat* root, int s){
        if (commoncontainer[s] >= root->say0)
            return -1;
        if (root->l == root->r){
            commoncontainer[s]++;
            return root->l;
        }
        if (root->lft->r >= l && root->lft->say0 - commoncontainer[(s << 1)]){
            int k = _first0(l, r, root->lft, s << 1);
            if (k != -1){
                commoncontainer[s]++;
                return k;
            }
        }
        if (root->rgt->l <= r && root->rgt->say0 - commoncontainer[(s << 1) | 1]){
            int k = _first0(l, r, root->rgt, (s << 1) | 1);
            if (k != -1){
                commoncontainer[s]++;
                return k;
            }
        }
        return -1;
    }

public:
    void init(int size, dat* root){
        commoncontainer.resize(size * 4);
        _init(root, 0, size);
    }

    void update(int l, int r, dat* root){
        _update(l, r, root);
    }

    int findleft0(dat* root, int l, int r){
        return _first0(l, r, root, 1);
    }

};


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> Q;
    Tree tre;
    vector<vector<array<int, 2>>> querys(N);
    vector<Tree::dat*> roots(N);
    for (int i = 0; i < Q; i++){
        int a, b, c;
        cin >> a >> b >> c;
        querys[c].push_back({ a, b });
    }
    roots[N - 1] = new Tree::dat;
    tre.init(N, roots[N - 1]);
    for (int i = N - 2; i >= 0; i--){
        roots[i] = new Tree::dat;
        tre.copy(roots[i + 1], roots[i]);
        for (auto j : querys[i + 1]){
            tre.update(j[0], j[1], roots[i]);
        }
    }
    vector<int> ret(N);
    for (int i = 0; i < N; i++){
        int l = 0, r = N - 1;
        for (auto o : querys[i]){
            l = max(l, o[0]);
            r = min(r, o[1]);
        }
        int k = tre.findleft0(roots[i], l, r);
        if (r < l || k == -1){
            for (int j = 0; j < N; j++){
                cout << -1 sp "";
            }
            return 0;
        }
        ret[k] = i;
    }
    for (auto u : ret){
        cout << u sp "";
    }
    return 0;
}

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