結果

問題 No.1675 Strange Minimum Query
ユーザー ripityripity
提出日時 2022-01-07 18:56:52
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 155 ms
56,596 KB
testcase_01 AC 128 ms
55,536 KB
testcase_02 AC 140 ms
55,420 KB
testcase_03 AC 1,705 ms
77,072 KB
testcase_04 AC 1,852 ms
84,624 KB
testcase_05 AC 776 ms
71,304 KB
testcase_06 AC 1,878 ms
83,784 KB
testcase_07 TLE -
testcase_08 AC 170 ms
56,428 KB
testcase_09 AC 272 ms
60,320 KB
testcase_10 AC 1,712 ms
86,016 KB
testcase_11 AC 844 ms
76,816 KB
testcase_12 AC 1,818 ms
89,508 KB
testcase_13 AC 1,683 ms
98,656 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 1,490 ms
87,608 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 1,733 ms
87,340 KB
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 1,611 ms
83,880 KB
testcase_29 AC 1,106 ms
79,116 KB
testcase_30 AC 1,030 ms
77,000 KB
testcase_31 WA -
testcase_32 TLE -
testcase_33 WA -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
権限があれば一括ダウンロードができます

ソースコード

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