結果

問題 No.1675 Strange Minimum Query
ユーザー ripityripity
提出日時 2022-01-07 18:56:52
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,729 bytes
コンパイル時間 3,264 ms
コンパイル使用メモリ 86,436 KB
実行使用メモリ 100,248 KB
最終ジャッジ日時 2024-11-14 05:19:26
合計ジャッジ時間 58,414 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 14 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
import java.io.*;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int N = sc.nextInt();
        int Q = sc.nextInt();
        boolean ok = true;
        int[] A = new int[N];
        Triplet[] tri = new Triplet[Q];
        TreeSet<Integer> tset = new TreeSet<>();
        SegmentTree smt = new SegmentTree();
        for( int i = 0; i < N; i++ ) {
            A[i] = 1000000000;
            smt.insert(i,A[i]);
            tset.add(i);
        }
        
        for( int i = 0; i < Q; i++ ) {
            int l = sc.nextInt()-1;
            int r = sc.nextInt()-1;
            int b = sc.nextInt();
            tri[i] = new Triplet(l,r,b);
        }
        
        Arrays.sort( tri, (t0,t1) -> t1.b-t0.b );
        for( int i = 0; i < Q; i++ ) {
            Triplet t = tri[i];
            if( tset.ceiling(t.l) == null || tset.ceiling(t.l) > t.r ) continue;
            while( !tset.isEmpty() && tset.ceiling(t.l) != null && tset.ceiling(t.l) <= t.r ) {
                int index = tset.ceiling(t.l);
                tset.remove(index);
                A[index] = t.b;
                smt.insert(index,A[index]);
            }
        }
        
        for( int i = 0; i < Q; i++ ) {
            Triplet t = tri[i];
            if( smt.rmq(t.l,t.r) != t.b ) ok = false;
        }
        
        if(ok) {
            for( int i = 0; i < N; i++ ) {
                if( i == N-1 ) pw.println(A[i]);
                else pw.print(A[i]+" ");
            }
        }else {
            pw.println(-1);
        }
        
        pw.flush();
        
    }
    
}

class SegmentTree {
    
    int N = 262144;
    int[] val;
    
    public SegmentTree() {
        
        this.val = new int[2*N+1];
        for( int i = 0; i < 2*N+1; i++ ) {
            val[i] = Integer.MAX_VALUE;
        }
        
    }
    
    public void insert(int id, int x) {
        
        id += N;
        val[id] = x;
        while( id > 1 ) {
            id >>= 1;
            val[id] = Math.min(val[(id<<1)|0],val[(id<<1)|1]);
        }
        
    }
    
    public int rmq(int l, int r) {
        
        int res = Integer.MAX_VALUE;
        l += N;
        r += N;
        while( l < r ) {
            if( l%2 == 1 ) res = Math.min(res,val[l++]);
            if( r%2 == 1 ) res = Math.min(res,val[--r]);
            l >>= 1;
            r >>= 1;
        }
        
        return res;
        
    }
    
}

class Triplet {
    
    int l,r,b;
    
    public Triplet(int l, int r, int b) {
        
        this.l = l;
        this.r = r;
        this.b = b;
        
    }
    
}
0