提出 #74603745 - AtCoder Weekday Contest 0039 Beta

コンテスト時間: 2026-04-02 20:00:00+0900 ~ 2026-04-02 21:00:00+0900 (60分) AtCoderホームへ戻る

提出 #74603745

ソースコード拡げる

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;

@SuppressWarnings("DuplicatedCode")
public class Main {
    static int MAX_STRING_LENGTH = (int) 1e6; // 字符串最大长度
    static int MAX_DIGIT_LENGTH = (int) 1e6; // 数位最大长度
    static int MOD7 = (int) 1e9 + 7, MOD8 = 80112002, MOD9 = 998244353, inf = Integer.MAX_VALUE;

    /***** 检查 T *****/
    static class Solution {

        void solve() {
            int n = io.nextInt(), m = io.nextInt(), q = io.nextInt(), k = io.nextInt();
            int[][] g = new int[m][];
            for (int i = 0; i < m; i++) {
                int id = io.nextInt(), page = io.nextInt();
                g[i] = new int[] {id, page};
            }

            Arrays.sort(g, (a, b) -> b[1] - a[1]);
            int[][] query = new int[q][];
            for (int i = 0; i < q; i++) {
                int l = io.nextInt(), r = io.nextInt(), t = io.nextInt();
                query[i] = new int[] {l, r, t, i};
            }
            Arrays.sort(query, (a, b) -> b[2] - a[2]);
            int[] ans = new int[q];
            int i = 0;
            Fenwick tree = new Fenwick(n + 1);
            for (int[] qu : query) {
                int l = qu[0], r = qu[1], t = qu[2], id = qu[3];
                while (i < m && g[i][1] >= t) {
                    tree.add(g[i][0], 1);
                    i++;
                }
                ans[id] = Math.max(tree.query(l, r) - k, 0);
            }
            for (int x : ans) {
                io.println(x);
            }
        }

        static class Fenwick {
            int[] tree;
            int n;

            Fenwick(int n) {
                tree = new int[n + 1];
                this.n = n + 1;
            }

            void add(int i, int v) {
                for (i++; i < n; i += i & -i) {
                    tree[i] += v;
                }
            }

            int query(int l, int r) {
                return pre(r) - pre(l - 1);
            }

            int pre(int i) {
                int s = 0;
                for (i++; i > 0; i &= i - 1) {
                    s += tree[i];
                }
                return s;
            }
        }


    }


    public static void main(String[] args) {
        io = new IO();
        int T = 1;
        // T = io.nextInt();
        for (; T > 0; T--) {
            new Solution().solve();
        }
        io.close();
    }

    static IO io;
    static class IO {
        BufferedInputStream bis = new BufferedInputStream(System.in);
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));

        int nextInt() {
            return (int) nextLong();
        }

        long nextLong() {
            try {
                long sign = 1, x = 0;
                int c = bis.read();
                while (c < '0' || c > '9') {
                    if (c == '-') sign = -1;
                    c = bis.read();
                }
                while (c >= '0' && c <= '9') {
                    x = x * 10 + (c - '0');
                    c = bis.read();
                }
                return sign * x;
            } catch (IOException e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                try {
                    int sign = 1, x = 0;
                    int c = bis.read();
                    while (c < '0' || c > '9') {
                        if (c == '-') sign = -1;
                        c = bis.read();
                    }
                    while (c >= '0' && c <= '9') {
                        x = x * 10 + (c - '0');
                        c = bis.read();
                    }
                    a[i] = sign * x;
                } catch (IOException e) {
                    throw new RuntimeException(e.getMessage());
                }
            }
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                try {
                    long sign = 1, x = 0;
                    int c = bis.read();
                    while (c < '0' || c > '9') {
                        if (c == '-') sign = -1;
                        c = bis.read();
                    }
                    while (c >= '0' && c <= '9') {
                        x = x * 10 + (c - '0');
                        c = bis.read();
                    }
                    a[i] = sign * x;
                } catch (IOException e) {
                    throw new RuntimeException(e.getMessage());
                }
            }
            return a;
        }

        int[] nextDigitArray(int n) {
            try {
                int[] a = new int[n];
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int i = 0;
                while (!ignore(x)) {
                    a[i++] = x - '0';
                    x = bis.read();
                }
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        private int[] DIGIT_ARRAY;

        int[] nextDigitArray() {
            try {
                if (DIGIT_ARRAY == null) {
                    DIGIT_ARRAY = new int[MAX_DIGIT_LENGTH];
                }
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int m = 0;
                while (!ignore(x)) {
                    DIGIT_ARRAY[m++] = x - '0';
                    x = bis.read();
                }
                int[] a = new int[m];
                System.arraycopy(DIGIT_ARRAY, 0, a, 0, m);
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        char nextChar() {
            try {
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                return (char) x;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        String[] nextStringArray(int n) {
            String[] a = new String[n];
            for (int i = 0; i < n; i++) {
                try {
                    if (CHAR_ARRAY == null) {
                        CHAR_ARRAY = new char[MAX_STRING_LENGTH];
                    }
                    int x = bis.read();
                    while (ignore(x)) {
                        x = bis.read();
                    }
                    int m = 0;
                    while (x != ' ' && x != ',' && !ignore(x)) {
                        CHAR_ARRAY[m++] = (char) x;
                        x = bis.read();
                    }
                    a[i] = new String(CHAR_ARRAY, 0, m);
                } catch (IOException e) {
                    throw new RuntimeException(e.getMessage());
                }
            }
            return a;
        }

        private char[] CHAR_ARRAY;

        char[] nextCharArray(boolean line) {
            try {
                if (CHAR_ARRAY == null) {
                    CHAR_ARRAY = new char[MAX_STRING_LENGTH];
                }
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int m = 0;
                while (line ? (x == ' ' || x == ',' || !ignore(x)) : !ignore(x)) {
                    CHAR_ARRAY[m++] = (char) x;
                    x = bis.read();
                }
                char[] a = new char[m];
                System.arraycopy(CHAR_ARRAY, 0, a, 0, m);
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        char[] nextCharArray(int n) {
            try {
                char[] a = new char[n];
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int i = 0;
                while (!ignore(x)) {
                    a[i++] = (char) x;
                    x = bis.read();
                }
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        private boolean ignore(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        String nextString(boolean line) {
            return new String(nextCharArray(line));
        }

        String nextString() {
            return nextString(false);
        }

        boolean nextBoolean() {
            return "true".equalsIgnoreCase(nextString());
        }

        double nextDouble() {
            return Double.parseDouble(nextString());
        }

        void println(Object obj) {
            print(obj);
            print("\n");
        }

        void println() {
            print('\n');
        }

        void print(Object obj) {
            pw.print(obj);
        }

        void printf(String format, Object... obj) {
            pw.printf(format, obj);
        }

        void close() {
            try {
                if (bis != null) bis.close();
                if (pw != null) {
                    pw.flush();
                    pw.close();
                }
                bis = null;
                pw = null;
            } catch (Exception ignore) {
            }
        }
    }
}

提出情報

提出日時	2026-04-02 20:48:10+0900
問題	E - 図書館の蔵書検索
ユーザ	gaoyuliang
言語	Java24 (OpenJDK 24.0.2)
得点	466
コード長	10116 Byte
結果	AC
実行時間	520 ms
メモリ	60336 KiB

ジャッジ結果

セット名

Sample

All

得点 / 配点

0 / 0

466 / 466

結果

× 5

× 94

セット名	テストケース
Sample	sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt
All	sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, in33.txt, in34.txt, in35.txt, in36.txt, in37.txt, in38.txt, in39.txt, in40.txt, in41.txt, in42.txt, in43.txt, in44.txt, in45.txt, in46.txt, in47.txt, in48.txt, in49.txt, in50.txt, in51.txt, in52.txt, in53.txt, in54.txt, in55.txt, in56.txt, in57.txt, in58.txt, in59.txt, in60.txt, in61.txt, in62.txt, in63.txt, in64.txt, in65.txt, in66.txt, in67.txt, in68.txt, in69.txt, in70.txt, in71.txt, in72.txt, in73.txt, in74.txt, in75.txt, in76.txt, in77.txt, in78.txt, in79.txt, in80.txt, in81.txt, in82.txt, in83.txt, in84.txt, in85.txt, in86.txt, in87.txt, in88.txt, in89.txt

ケース名	結果	実行時間	メモリ
in01.txt	AC	56 ms	38716 KiB
in02.txt	AC	51 ms	38500 KiB
in03.txt	AC	51 ms	38500 KiB
in04.txt	AC	52 ms	38480 KiB
in05.txt	AC	52 ms	38476 KiB
in06.txt	AC	52 ms	38448 KiB
in07.txt	AC	52 ms	38468 KiB
in08.txt	AC	53 ms	38628 KiB
in09.txt	AC	51 ms	38704 KiB
in10.txt	AC	470 ms	58388 KiB
in11.txt	AC	485 ms	58272 KiB
in12.txt	AC	477 ms	60244 KiB
in13.txt	AC	189 ms	46116 KiB
in14.txt	AC	466 ms	58340 KiB
in15.txt	AC	494 ms	57912 KiB
in16.txt	AC	319 ms	57216 KiB
in17.txt	AC	210 ms	55816 KiB
in18.txt	AC	307 ms	57512 KiB
in19.txt	AC	52 ms	38588 KiB
in20.txt	AC	273 ms	56052 KiB
in21.txt	AC	310 ms	58312 KiB
in22.txt	AC	470 ms	59664 KiB
in23.txt	AC	279 ms	55968 KiB
in24.txt	AC	274 ms	57096 KiB
in25.txt	AC	308 ms	58304 KiB
in26.txt	AC	301 ms	57488 KiB
in27.txt	AC	276 ms	56360 KiB
in28.txt	AC	477 ms	60048 KiB
in29.txt	AC	304 ms	56144 KiB
in30.txt	AC	425 ms	59444 KiB
in31.txt	AC	52 ms	38524 KiB
in32.txt	AC	52 ms	38604 KiB
in33.txt	AC	52 ms	38780 KiB
in34.txt	AC	63 ms	39188 KiB
in35.txt	AC	52 ms	38628 KiB
in36.txt	AC	54 ms	38472 KiB
in37.txt	AC	52 ms	38592 KiB
in38.txt	AC	52 ms	38508 KiB
in39.txt	AC	54 ms	38436 KiB
in40.txt	AC	55 ms	38444 KiB
in41.txt	AC	479 ms	59748 KiB
in42.txt	AC	491 ms	59852 KiB
in43.txt	AC	51 ms	38776 KiB
in44.txt	AC	51 ms	38564 KiB
in45.txt	AC	52 ms	38488 KiB
in46.txt	AC	53 ms	38248 KiB
in47.txt	AC	51 ms	38660 KiB
in48.txt	AC	52 ms	38428 KiB
in49.txt	AC	52 ms	38360 KiB
in50.txt	AC	418 ms	59472 KiB
in51.txt	AC	484 ms	60336 KiB
in52.txt	AC	484 ms	59976 KiB
in53.txt	AC	484 ms	59224 KiB
in54.txt	AC	520 ms	60184 KiB
in55.txt	AC	480 ms	58784 KiB
in56.txt	AC	489 ms	59948 KiB
in57.txt	AC	344 ms	57604 KiB
in58.txt	AC	485 ms	60208 KiB
in59.txt	AC	500 ms	58456 KiB
in60.txt	AC	501 ms	59188 KiB
in61.txt	AC	501 ms	58320 KiB
in62.txt	AC	502 ms	60092 KiB
in63.txt	AC	505 ms	59804 KiB
in64.txt	AC	495 ms	58224 KiB
in65.txt	AC	382 ms	57060 KiB
in66.txt	AC	507 ms	59800 KiB
in67.txt	AC	450 ms	57548 KiB
in68.txt	AC	51 ms	38864 KiB
in69.txt	AC	51 ms	38440 KiB
in70.txt	AC	51 ms	38440 KiB
in71.txt	AC	51 ms	38352 KiB
in72.txt	AC	52 ms	38708 KiB
in73.txt	AC	51 ms	38696 KiB
in74.txt	AC	109 ms	42928 KiB
in75.txt	AC	108 ms	42736 KiB
in76.txt	AC	51 ms	38476 KiB
in77.txt	AC	52 ms	38560 KiB
in78.txt	AC	51 ms	38504 KiB
in79.txt	AC	51 ms	38352 KiB
in80.txt	AC	216 ms	54400 KiB
in81.txt	AC	203 ms	54144 KiB
in82.txt	AC	52 ms	38660 KiB
in83.txt	AC	52 ms	38304 KiB
in84.txt	AC	51 ms	38612 KiB
in85.txt	AC	51 ms	38660 KiB
in86.txt	AC	52 ms	38616 KiB
in87.txt	AC	51 ms	38648 KiB
in88.txt	AC	517 ms	59864 KiB
in89.txt	AC	460 ms	58940 KiB
sample01.txt	AC	52 ms	38440 KiB
sample02.txt	AC	51 ms	38632 KiB
sample03.txt	AC	52 ms	38532 KiB
sample04.txt	AC	52 ms	38296 KiB
sample05.txt	AC	50 ms	38576 KiB