結果

問題 No.1012 荷物収集
ユーザー ks2m
提出日時 2020-03-20 22:34:05
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 1,841 bytes
コンパイル時間 3,655 ms
コンパイル使用メモリ 80,504 KB
実行使用メモリ 73,756 KB
最終ジャッジ日時 2024-12-15 06:55:23
合計ジャッジ時間 26,219 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 9 WA * 32
権限があれば一括ダウンロードができます

ソースコード

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int q = Integer.parseInt(sa[1]);
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.x = Integer.parseInt(sa[0]);
            o.w = Integer.parseInt(sa[1]);
            arr[i] = o;
        }
        sa = br.readLine().split(" ");
        Query[] qu = new Query[q];
        for (int i = 0; i < q; i++) {
            Query o = new Query();
            o.i = i;
            o.x = Integer.parseInt(sa[i]);
            qu[i] = o;
        }
        br.close();
        Arrays.parallelSort(arr, (o1, o2) -> o1.x - o2.x);
        Arrays.parallelSort(qu, (o1, o2) -> o1.x - o2.x);
        long right = 0;
        for (int i = 0; i < n; i++) {
            right += arr[i].w;
        }
        int pre = 0;
        int idx = 0;
        long left = 0;
        for (int i = 0; i < q; i++) {
            long val = left * (qu[i].x - pre);
            if (i > 0) {
                val += qu[i - 1].ans;
            }
            while (idx < n) {
                Obj o = arr[idx];
                if (o.x <= qu[i].x) {
                    val += (qu[i].x - o.x) * o.w;
                    if (i > 0) {
                        val -= (o.x - qu[i - 1].x) * o.w;
                    }
                    left += o.w;
                    right -= o.w;
                    idx++;
                } else {
                    break;
                }
            }
            if (i == 0) {
                for (int j = idx; j < n; j++) {
                    val += (arr[j].x - qu[i].x) * arr[j].w;
                }
            } else {
                val -= right * (qu[i].x - pre);
            }
            qu[i].ans = val;
            pre = qu[i].x;
        }
        Arrays.parallelSort(qu, (o1, o2) -> o1.i - o2.i);
        PrintWriter pw = new PrintWriter(System.out);
        for (Query o : qu) {
            pw.println(o.ans);
        }
        pw.flush();
    }
    static class Obj {
        int x, w;
    }
    static class Query {
        int i, x;
        long ans;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0