結果

問題 No.568 じゃんじゃん　落とす　委員会
ユーザー nebukuro09nebukuro09
提出日時 2017-09-09 00:16:26
言語 D
(dmd 2.106.1)
結果
TLE  
実行時間 -
コード長 3,369 bytes
コンパイル時間 891 ms
コンパイル使用メモリ 129,956 KB
実行使用メモリ 13,364 KB
最終ジャッジ日時 2024-06-12 21:50:49
合計ジャッジ時間 24,616 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 133 ms
8,232 KB
testcase_01 AC 135 ms
9,272 KB
testcase_02 TLE -
testcase_03 TLE -
testcase_04 TLE -
testcase_05 AC 6 ms
7,576 KB
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 AC 5 ms
6,944 KB
testcase_10 AC 5 ms
7,856 KB
testcase_11 TLE -
testcase_12 AC 131 ms
9,532 KB
testcase_13 TLE -
testcase_14 AC 977 ms
9,656 KB
testcase_15 TLE -
testcase_16 AC 833 ms
11,380 KB
testcase_17 AC 127 ms
11,672 KB
testcase_18 TLE -
testcase_19 TLE -
testcase_20 AC 316 ms
9,608 KB
testcase_21 TLE -
testcase_22 AC 133 ms
9,072 KB
testcase_23 TLE -
testcase_24 AC 5 ms
6,944 KB
testcase_25 AC 5 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

alias Tuple!(int, "a", int, "b") Score;
const int MAX = 10^^5 + 10;

void main() {
    auto t = readln.split.map!(to!int);
    auto N = t[0];
    auto M = t[1];
    Score[] s0;
    Score[] s1;
    Score[] s2;
    int cnt2 = 0;
    int cnt3 = 0;
    foreach (i; 0..N) {
        t = readln.split.map!(to!int);
        if (t[0] == 0)
            s0 ~= Score(t[1], t[2]);
        else if (t[0] == 1)
            s1 ~= Score(t[1], t[2]);
        else if (t[0] == 2)
            s2 ~= Score(t[1], t[2]), cnt2 += 1;
        else
            cnt2 += 1, cnt3 += 1;
    }


    int ans = 1 << 29;
    s0.sort!"a[0] < b[0]";
    s1.sort!"a[0] < b[0]";
    s2.sort!"a[0] < b[0]";
    auto st0 = new SegmentTree(MAX);
    auto st1a = new SegmentTree(MAX);
    auto st1b = new SegmentTree(MAX);
    auto st2 = new SegmentTree(MAX);
    int p0 = s0.length.to!int - 1;
    int p1 = s1.length.to!int - 1;
    int p2 = s2.length.to!int - 1;

    foreach (s; s1)
        st1b.add(s.b, 1);
    foreach (s; s2)
        st2.add(s.b, 1);


    for (int a = MAX - 1; a >= 0; --a) {

        for (; p0 >= 0 && s0[p0].a == a; p0--)
            st0.add(s0[p0].b, 1);
        for (; p1 >= 0 && s1[p1].a == a; p1--) {
            st1a.add(s1[p1].b, 1);
            st1b.add(s1[p1].b, -1);
            cnt2 += 1;
        }
        for (; p2 >= 0 && s2[p2].a == a; p2--) {
            st2.add(s2[p2].b, -1);
            cnt3 += 1;
        }

        int target = M - cnt2;
        if (target <= 0) {
            ans = min(ans, cnt3);
            continue;
        }

        int hi = MAX-1;
        int lo = -1;
        while (hi - lo > 1) {
            int mid = (hi + lo) / 2;
            int tmp2 = 0;
            tmp2 += st0.sum(mid, MAX);
            tmp2 += st1b.sum(mid, MAX);
            if (tmp2 < target)
                hi = mid;
            else
                lo = mid;
        }

        if (lo == -1)
            continue;

        int tmp3 = 0;
        tmp3 += st1a.sum(lo, MAX);
        tmp3 += st2.sum(lo, MAX);
        ans = min(ans, cnt3 + tmp3);
        //if (a <= 100)
        //    writeln([a, lo, cnt2, cnt3, tmp3, ans, st0.sum(lo,MAX)+st1b.sum(lo,MAX), p0, p1, p2]);
    }

    ans.writeln;
}


class SegmentTree {
    int[] table;
    int size;

    this(int n) {
        assert(bsr(n) < 29);
        size = 1 << (bsr(n) + 2);
        table = new int[](size);
    }

    void add(int pos, int num) {
        return add(pos, num, 0, 0, size/2-1);
    }

    void add(int pos, int num, int i, int left, int right) {
        table[i] += num;
        if (left == right)
            return;
        auto mid = (left + right) / 2;
        if (pos <= mid)
            add(pos, num, i*2+1, left, mid);
        else
            add(pos, num, i*2+2, mid+1, right);
    }

    int sum(int pl, int pr) {
        return sum(pl, pr, 0, 0, size/2-1);
    }

    int sum(int pl, int pr, int i, int left, int right) {
        if (pl > right || pr < left)
            return 0;
        else if (pl <= left && right <= pr)
            return table[i];
        else
            return
                sum(pl, pr, i*2+1, left, (left+right)/2) +
                sum(pl, pr, i*2+2, (left+right)/2+1, right);
    }
}
0