結果

問題 No.1982 [Cherry 4th Tune B] 絶険
コンテスト
ユーザー tenten
提出日時 2022-06-23 09:19:36
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 3,445 bytes
コンパイル時間 2,694 ms
コンパイル使用メモリ 78,684 KB
実行使用メモリ 75,440 KB
最終ジャッジ日時 2024-11-06 23:17:03
合計ジャッジ時間 11,639 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner();
        int n = sc.nextInt();
        int k = sc.nextInt();
        int q = sc.nextInt();
        SegmentTree st = new SegmentTree(n);
        for (int i = 0; i < k; i++) {
            st.update(new Wall(i, sc.nextInt() - 1, sc.nextInt() - 1, sc.nextInt(), sc.nextInt()));
        }
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Wall> queue = new PriorityQueue<>();
        while (q-- > 0) {
            int idx = sc.nextInt() - 1;
            long height = sc.nextLong();
            st.query(idx, queue);
            while(queue.size() > 0) {
                Wall w = queue.poll();
                height -= w.height;
                if (height <= 0) {
                    sb.append(w.color).append("\n");
                    break;
                }
            }
            if (height > 0) {
                sb.append("-1\n");
            }
            queue.clear();
        }
        System.out.print(sb);
    }
}
class Wall implements Comparable<Wall> {
    int idx;
    int left;
    int right;
    int height;
    int color;
    
    public Wall(int idx, int left, int right, int color, int height) {
        this.idx = idx;
        this.left = left;
        this.right = right;
        this.height = height;
        this.color = color;
    }
    
    public int compareTo(Wall another) {
        return idx - another.idx;
    }
}
class SegmentTree {
    static final int INF = Integer.MAX_VALUE;
    int size;
    int base;
    ArrayList<ArrayList<Wall>> tree = new ArrayList<>();

    public SegmentTree(int size) {
        this.size = size;
        base = 1;
        while (base < size) {
            base <<= 1;
        }
        for (int i = 0; i < base * 2 - 1; i++) {
            tree.add(new ArrayList<>());
        }
    }
    
    public void query(int idx, PriorityQueue<Wall> queue) {
        queryTree(idx + base - 1, queue);
    }
    
    public void queryTree(int idx, PriorityQueue<Wall> queue) {
        queue.addAll(tree.get(idx));
        if (idx == 0) {
            return;
        }
        queryTree((idx - 1) / 2, queue);
    }
    
    public void update(Wall wall) {
        updateTree(0, 0, base, wall);
    }
    
    public void updateTree(int idx, int left, int right, Wall wall) {
        if (wall.left >= right || wall.right < left) {
            return;
        }
        if (wall.left <= left && right - 1 <= wall.right) {
            tree.get(idx).add(wall);
            return;
        }
        updateTree(2 * idx + 1, left, (left + right) / 2, wall);
        updateTree(2 * idx + 2, (left + right) / 2, right, wall);
    }
    
 }
class Scanner {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer("");
    
    public Scanner() throws Exception {
        
    }
    
    public int nextInt() throws Exception {
        return Integer.parseInt(next());
    }
    
    public long nextLong() throws Exception {
        return Long.parseLong(next());
    }
    
    public double nextDouble() throws Exception {
        return Double.parseDouble(next());
    }
    
    public String next() throws Exception {
        if (!st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }
}
0