結果

問題 No.1675 Strange Minimum Query
ユーザー nawawannawawan
提出日時 2021-09-10 23:17:22
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 306 ms / 2,000 ms
コード長 4,394 bytes
コンパイル時間 2,546 ms
コンパイル使用メモリ 213,824 KB
実行使用メモリ 17,936 KB
最終ジャッジ日時 2023-09-02 21:39:23
合計ジャッジ時間 13,554 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,372 KB
testcase_01 AC 2 ms
4,372 KB
testcase_02 AC 1 ms
4,368 KB
testcase_03 AC 171 ms
7,356 KB
testcase_04 AC 166 ms
10,236 KB
testcase_05 AC 52 ms
10,228 KB
testcase_06 AC 201 ms
8,048 KB
testcase_07 AC 219 ms
10,032 KB
testcase_08 AC 1 ms
4,372 KB
testcase_09 AC 3 ms
4,368 KB
testcase_10 AC 177 ms
12,764 KB
testcase_11 AC 65 ms
11,080 KB
testcase_12 AC 201 ms
14,024 KB
testcase_13 AC 261 ms
17,788 KB
testcase_14 AC 293 ms
17,868 KB
testcase_15 AC 272 ms
17,876 KB
testcase_16 AC 1 ms
4,372 KB
testcase_17 AC 47 ms
6,488 KB
testcase_18 AC 64 ms
6,996 KB
testcase_19 AC 117 ms
14,268 KB
testcase_20 AC 185 ms
13,408 KB
testcase_21 AC 183 ms
15,408 KB
testcase_22 AC 224 ms
16,408 KB
testcase_23 AC 158 ms
8,792 KB
testcase_24 AC 155 ms
11,884 KB
testcase_25 AC 109 ms
7,852 KB
testcase_26 AC 67 ms
8,708 KB
testcase_27 AC 173 ms
15,920 KB
testcase_28 AC 100 ms
12,136 KB
testcase_29 AC 95 ms
13,664 KB
testcase_30 AC 67 ms
8,788 KB
testcase_31 AC 200 ms
10,064 KB
testcase_32 AC 283 ms
17,720 KB
testcase_33 AC 280 ms
17,936 KB
testcase_34 AC 286 ms
17,924 KB
testcase_35 AC 305 ms
17,912 KB
testcase_36 AC 306 ms
17,880 KB
権限があれば一括ダウンロードができます

ソースコード

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