結果

問題 No.789 範囲の合計
ユーザー Oland
提出日時 2019-05-24 12:34:24
言語 Java
(openjdk 23)
結果
AC  
実行時間 632 ms / 1,000 ms
コード長 5,434 bytes
コンパイル時間 2,568 ms
コンパイル使用メモリ 83,356 KB
実行使用メモリ 73,572 KB
最終ジャッジ日時 2024-09-17 10:06:10
合計ジャッジ時間 10,586 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.*;
import java.util.*;
import java.util.Map.Entry;
import java.util.stream.Collectors;
@SuppressWarnings("unused")
public class Main {
    
    //final boolean isDebug = true;
    final boolean isDebug = false;
    String fileName = "input.txt";
    FastScanner sc;
    PrintWriter out;
    final int MOD = (int)1e9+7;
    //final int INF = Integer.MAX_VALUE / 2;
    final long INF = Long.MAX_VALUE / 2;
    
    void solve() throws Exception{
        int n = sc.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        int[] q = new int[n], x = new int[n], y = new int[n];
        for(int i = 0; i < n; i++){
            q[i] = sc.nextInt(); x[i] = sc.nextInt(); y[i] = sc.nextInt();
            list.add(x[i]); list.add(y[i]);
        }
        
        ArrayList<Integer> su = compress(list);
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < su.size(); i++) map.put(su.get(i), i+1);
        
        BinaryIndexedTree bit = new BinaryIndexedTree(su.size());
        long ans = 0;
        for(int i = 0; i < n; i++){
            if(q[i] == 0){
                bit.add(map.get(x[i]), y[i]);
            }else{
                ans += bit.getSum(map.get(x[i]), map.get(y[i]));
            }
        }
        System.out.println(ans);
    }
    
    ArrayList<Integer> compress(ArrayList<Integer> list){
        ArrayList<Integer> sortedUniqueList = new ArrayList<>(list.stream().sorted().distinct().collect(Collectors.toList()));
        return sortedUniqueList;
    }
    
    /* end solve */
    
    /* main */
    public static void main(String[] args) throws Exception {
        new Main().m();
    }
    
    void m() throws Exception {
        long S = System.currentTimeMillis();
        sc = (isDebug) ? new FastScanner(new FileInputStream(fileName)) : new FastScanner(System.in);
        out = new PrintWriter(System.out);
        solve();
        out.flush();
        long G = System.currentTimeMillis();
        if(isDebug){
            System.out.println("---Debug---");
            System.out.printf("%8d ms\n", (G-S));
        }
    }
    /* end main */
}
/* end Main */
/*
 * BIT(BinaryIndexedTree)
 * 1-indexed、範囲指定するときは[a,b]
 * RSQ(要素加算、区間和クエリ)による実装
 */
class BinaryIndexedTree{
    int n;
    int[] node;
    
    /* 初期値は0 */
    public BinaryIndexedTree(int n){
        this.n = n;
        node = new int[n+1];
    }
    
    /* 1-indexed */
    public void add(int x, int val){
        for(int i = x; i <= n; i += (i & -i)){
            node[i] += val;
        }
    }
    
    /* 
     * [1,a], 1-indexed
     * sum(0) == 0
     */
    public int getSum(int a){
        int res = 0;
        for(int i = a; i > 0; i -= (i & -i)){
            res += node[i];
        }
        return res;
    }
    
    /* [a,b], 1-indexed */
    public int getSum(int a, int b){
        return getSum(b) - getSum(a-1);
    }
    
    /*
    //[a,b), 1-indexed
    public int sum(int a, int b){
        return sum(b-1) - sum(a-1);
    }
    */
    
    /*
     * 小さいほうからk番目の値を二分探索で求める
     * 1-indexed
     */
    public int getKth(int k){
        if(k <= 0) return 0;
        int res = 0;
        int N = 1; while(N < node.length) N *= 2;
        for(int i = N / 2; i > 0; i /= 2){
            if(res + i < node.length && node[res + i] < k){
                k -= node[res + i];
                res += i;
            }
        }
        return res+1;
    }
}
class FastScanner {
    private InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    public FastScanner(InputStream in) {
        this.in = in;
    }
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() {
        if (hasNextByte()) return buffer[ptr++];
        else return -1;
    }
    private static boolean isPrintableChar(int c){
        return 33 <= c && c <= 126;
    }
    public boolean hasNext() {
        while(hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++; return hasNextByte();
    }
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public String nextLine() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(b != 10) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() {
        return Double.parseDouble(next());
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0