結果

問題 No.1675 Strange Minimum Query
ユーザー nawawannawawan
提出日時 2021-09-10 22:31:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,618 bytes
コンパイル時間 2,814 ms
コンパイル使用メモリ 210,080 KB
実行使用メモリ 10,488 KB
最終ジャッジ日時 2023-09-02 18:57:16
合計ジャッジ時間 13,707 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,368 KB
testcase_01 AC 2 ms
4,368 KB
testcase_02 AC 1 ms
4,368 KB
testcase_03 AC 275 ms
6,216 KB
testcase_04 AC 248 ms
7,008 KB
testcase_05 AC 20 ms
5,540 KB
testcase_06 AC 326 ms
6,800 KB
testcase_07 AC 348 ms
7,648 KB
testcase_08 AC 2 ms
4,372 KB
testcase_09 AC 3 ms
4,372 KB
testcase_10 AC 164 ms
6,924 KB
testcase_11 AC 55 ms
5,748 KB
testcase_12 AC 188 ms
7,604 KB
testcase_13 AC 329 ms
10,236 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 1 ms
4,368 KB
testcase_17 AC 67 ms
4,628 KB
testcase_18 WA -
testcase_19 AC 141 ms
7,340 KB
testcase_20 AC 302 ms
8,036 KB
testcase_21 WA -
testcase_22 AC 358 ms
9,180 KB
testcase_23 WA -
testcase_24 AC 251 ms
6,956 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 127 ms
6,548 KB
testcase_29 AC 95 ms
6,720 KB
testcase_30 WA -
testcase_31 AC 356 ms
7,444 KB
testcase_32 AC 473 ms
10,292 KB
testcase_33 AC 472 ms
10,296 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
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){
    if(x == INF) return y;
    else if(y != INF) return y;
    return x;
}
int FX(int x, int y){
    if(y == INF) return x;
    return y;
}
int e(){
    return INF;
}
int main(){
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N, INF);
    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]]);
    }
    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.query(i, i + 1) << ' ';
        else cout << seg.query(i, i + 1) << endl;
    }
}
0