結果

問題 No.1675 Strange Minimum Query
ユーザー nawawannawawan
提出日時 2021-09-11 02:31:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 406 ms / 2,000 ms
コード長 6,492 bytes
コンパイル時間 3,690 ms
コンパイル使用メモリ 210,736 KB
実行使用メモリ 10,240 KB
最終ジャッジ日時 2024-06-13 01:47:36
合計ジャッジ時間 13,899 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 175 ms
6,940 KB
testcase_04 AC 145 ms
7,040 KB
testcase_05 AC 14 ms
6,944 KB
testcase_06 AC 196 ms
7,040 KB
testcase_07 AC 205 ms
7,680 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 3 ms
6,944 KB
testcase_10 AC 152 ms
7,168 KB
testcase_11 AC 45 ms
6,944 KB
testcase_12 AC 168 ms
7,808 KB
testcase_13 AC 315 ms
10,240 KB
testcase_14 AC 353 ms
10,240 KB
testcase_15 AC 335 ms
10,240 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 57 ms
6,940 KB
testcase_18 AC 81 ms
6,940 KB
testcase_19 AC 117 ms
7,296 KB
testcase_20 AC 243 ms
7,808 KB
testcase_21 AC 230 ms
8,448 KB
testcase_22 AC 294 ms
9,088 KB
testcase_23 AC 230 ms
6,944 KB
testcase_24 AC 208 ms
7,296 KB
testcase_25 AC 150 ms
6,940 KB
testcase_26 AC 78 ms
6,944 KB
testcase_27 AC 197 ms
8,448 KB
testcase_28 AC 106 ms
6,944 KB
testcase_29 AC 81 ms
6,940 KB
testcase_30 AC 77 ms
6,940 KB
testcase_31 AC 303 ms
7,296 KB
testcase_32 AC 401 ms
10,240 KB
testcase_33 AC 404 ms
10,240 KB
testcase_34 AC 402 ms
10,240 KB
testcase_35 AC 406 ms
10,240 KB
testcase_36 AC 393 ms
10,240 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
template<typename S, S (*XX)(S, S), S (*id)(), typename F, F (*FF)(F, F), S (*FX)(F, S), F (*e)()> struct lazy_segment_tree{
private:
    int n;
    int size;//元の配列の大きさ
    int height; //セグ木の高さの最大値 - 1
    vector<S> dat;
    vector<F> lazy;
    void update_sub(int k){
        dat[k] = XX(dat[k << 1 | 0], dat[k << 1 | 1]);
    }
    //伝搬用の関数
    void push(int k){
        operate(2 * k, lazy[k]);
        operate(2 * k + 1, lazy[k]);
        lazy[k] = e();
    }
    //伝搬してきた遅延を作用させ、遅延部分を増幅(というより結合)させる
    void operate(int k, F x){
        dat[k] = FX(x, dat[k]);
        if(k < size) lazy[k] = FF(x, lazy[k]);
    }
public:
    lazy_segment_tree(int n_) : n(n_ * 2), size(n_){
        dat.resize(n, id());
        lazy.resize(n, e());
        height = 0;
        int t = 1;
        while(t < n_){
            height++;
            t *= 2;
        }
    }
    lazy_segment_tree(vector<S> &v){
        size = (int)v.size();
        n = size * 2;
        dat.resize(n, id());
        height = 0;
        int t = 1;
        while(t < size){
            t *= 2;
            height++;
        }
        lazy.resize(n, e());
        for(int i = 0; i < size; i++) dat[i + size] = v[i];
        for(int i = size - 1; i >= 1; i--){
            update_sub(i);
        }
    }
    //区間更新
    void update(int l, int r, F a){
        int l1 = l + size;
        int r1 = r + size;
        for(int i = height; i >= 1; i--){
            if(((l1 >> i) << i) != l1 && (l1 >> i) >= 1) push(l1 >> i);
            if(((r1 >> i) << i) != r1 && (r1 >> i) >= 1) push(r1 >> i);
        }
        while(r1 > l1){
            if(l1 & 1) operate(l1++, a);
            if(r1 & 1) operate(--r1, a);
            r1 >>= 1;
            l1 >>= 1;
        }
        l1 = l + size;
        r1 = r + size;
        for(int i = 1; i <= height; i++){
            if(((l1 >> i) << i) != l1 && (l1 >> i) >= 1) update_sub(l1 >> i);
            if(((r1 >> i) << i) != r1 && (r1 >> i) >= 1) update_sub(r1 >> i);
        }
    }
    //一点更新
    void update(int ind, F a){
        ind += size;
        for(int i = height; i >= 1; i--){
            if((ind >> i) >= 1) push(ind >> i);
        }
        dat[ind] = FX(a, dat[ind]);
        for(int i = 1; i <= height; i++){
            if((ind >> i) >= 1) update_sub(ind >> i);
        }
    }
    //区間mergeを取得
    S query(int l, int r){
        if(l >= r) return id();
        S resr = id(), resl = id();
        l += size;
        r += size;
        for(int i = height; i >= 1; i--){
            if(((l >> i) << i) != l && (l >> i) >= 1) push(l >> i);
            if(((r >> i) << i) != r && (r >> i) >= 1) push(r >> i);
        }
        while(r > l){
            if(l & 1) resl = XX(resl, dat[l++]);
            if(r & 1) resr = XX(dat[--r], resr);
            l >>= 1;
            r >>= 1;
        }
        return XX(resl, resr);
    }
    S all_query(){
        return dat[1];
    }
    //[l, r)でf(merge(a[l],..., a[r - 1]))がtrueとなる最大のrを返す
    template<typename op>
    int max_right(int l, op f){
        if(l == size) return size;
        stack<int> s;
        queue<int> q;
        l += size;
        int r = n;
        for(int i = height; i >= 1; i--){
            if(((l >> i) << i) != l && (l >> i) >= 1) push(l >> i);
        }
        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){
            push(now);
            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 op>
    int min_left(int r, op f){
        if(r == 0) return 0;
        stack<int> s;
        queue<int> q;
        int l = size;
        r += size;
        for(int i = height; i >= 1; i--){
            if(((r >> i) << i) != r && (r >> i) >= 1) push(r >> i);
        }
        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){
            push(now);
            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 FF(int x, int y){
    return max(x, y);
}
int FX(int x, int y){
    return max(x, y);
}
int e(){
    return 0;
}
int main(){
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N, 1);
    lazy_segment_tree<int, XX, id, int, FF, FX, e> 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];
    });
    for(int i = 0; i < Q; i++){
        seg.update(L[ind[i]], R[ind[i]], B[ind[i]]);
        int te = seg.query(L[ind[i]], R[ind[i]]);
        if(te != B[ind[i]]){
            cout << -1 << endl;
            return 0;
        }
    }
    for(int i = 0; i < N; i++){
        if(i != N - 1) cout << seg.query(i, i + 1) << ' ';
        else cout << seg.query(i, i + 1) << endl; 
    }
}
0