結果

問題 No.1675 Strange Minimum Query
ユーザー nawawan
提出日時 2021-09-10 23:17:22
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 379 ms / 2,000 ms
コード長 4,394 bytes
コンパイル時間 2,736 ms
コンパイル使用メモリ 206,796 KB
最終ジャッジ日時 2025-01-24 12:18:52
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
template<typename S, S (*XX)(S, S), S (*id)()> struct segment_tree{
private:
    int n;
    int size;//元の配列の大きさ
    vector<S> dat;
    void update_sub(int k){
        dat[k] = XX(dat[k << 1 | 0], dat[k << 1 | 1]);
    }
public:
    segment_tree(int n_) : n(n_ * 2), size(n_){
        dat.resize(n, id());
    }
    segment_tree(vector<S> &v){
        size = (int)v.size();
        n = size * 2;
        dat.resize(n, id());
        for(int i = 0; i < size; ++i) dat[i + size] = v[i];
        for(int i = size - 1; i >= 1; --i){
            update_sub(i);
        }
    }
    S& operator[](const int i){
        return dat[i + size];
    }
    void update(int ind, S a){
        ind += size;
        dat[ind] = a;
        while(ind > 1){
            ind >>= 1;
            dat[ind] = XX(dat[ind << 1 | 0], dat[ind << 1 | 1]);
        }
    }
    S query(int l, int r){
        if(l >= r) return id();
        S vl = id(), vr = id();
        l += size;
        r += size;
        while(r > l){
            if(l & 1) vl = XX(vl, dat[l++]);
            if(r & 1) vr = XX(dat[--r], vr);
            l >>= 1;
            r >>= 1;
        }
        return XX(vl, vr);
    }
    //[l, r)でf(merge(a[l],..., a[r - 1]))がtrueとなる最大のrを返す
    template<typename F>
    int max_right(int l, F f){
        if(l == size) return size;
        stack<int> s;
        queue<int> q;
        l += size;
        int r = n;
        while(r > l){
            if(l & 1) q.push(l++);
            if(r & 1) s.push(--r);
            r >>= 1;
            l >>= 1;
        }
        while(!s.empty()){
            q.push(s.top());
            s.pop();
        }
        S res = id();
        int now = -1;
        while(!q.empty()){
            int v = q.front();
            q.pop();
            S temp = XX(res, dat[v]);
            if(!f(temp)){
                now = v;
                break;
            }
            res = temp;
        }
        if(now == -1) return size;
        while(now < size){
            now <<= 1;
            S temp = XX(res, dat[now]);
            if(f(temp)){
                res = temp;
                ++now;
            }
        }
        return now - size;
    }
    //[l, r)でf(merge(a[l],..., a[r - 1]))がtrueとなる最小のlを返す
    template<typename F>
    int min_left(int r, F f){
        if(r == 0) return 0;
        stack<int> s;
        queue<int> q;
        int l = size;
        r += size;
        while(r > l){
            if(r & 1) q.push(--r);
            if(l & 1) s.push(l++);
            r >>= 1;
            l >>= 1;
        }
        while(!s.empty()){
            q.push(s.top());
            s.pop();
        }
        S res = id();
        int now = -1;
        while(!q.empty()){
            int v = q.front();
            q.pop();
            S temp = XX(res, dat[v]);
            if(!f(temp)){
                now = v;
                break;
            }
            res = temp;
        }
        if(now == -1) return 0;
        while(now < size){
            now <<= 1;
            ++now;
            S temp = XX(res, dat[now]);
            if(f(temp)){
                res = temp;
                --now;
            }
        }
        return now + 1 - size;
    }
};
int INF = 1000000000;
int XX(int x, int y){
    return min(x, y);
}
int id(){
    return INF;
}
int main(){
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N, INF);
    segment_tree<int, XX, id> seg(A);
    vector<int> L(Q), R(Q), B(Q);
    for(int i = 0; i < Q; i++) {
        cin >> L[i] >> R[i] >> B[i];
        L[i]--;
    }
    vector<int> ind(Q);
    iota(ind.begin(), ind.end(), 0);
    sort(ind.begin(), ind.end(), [&](int x, int y){
        return B[x] > B[y];
    });
    set<int> s;
    for(int i = 0; i < N; i++) s.insert(i);
    s.insert(-1);
    s.insert(N);
    for(int i = 0; i < Q; i++){
        auto ite = s.lower_bound(L[ind[i]]);
        for(ite; *ite < R[ind[i]]; ){
            seg.update(*ite, B[ind[i]]);
            ite = s.erase(ite);
        }
    }
    for(int i = 0; i < Q; i++){
        int temp = seg.query(L[i], R[i]);
        if(temp != B[i]){
            cout << -1 << endl;
            return 0;
        }
    }
    for(int i = 0; i < N; i++){
        if(i != N - 1) cout << seg[i] << ' ';
        else cout << seg[i] << endl;
    }
}
0