結果

問題 No.568 じゃんじゃん　落とす　委員会
コンテスト
ユーザー zhuqingyun0510
提出日時 2025-08-29 12:12:24
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,001 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,141 ms
コンパイル使用メモリ 213,920 KB
実行使用メモリ 13,784 KB
最終ジャッジ日時 2026-07-14 12:30:31
合計ジャッジ時間 3,814 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 100010, M = 200000, A = 100001;

int n, m, x[N], a[N], b[N], t1[M + 5], t2[M + 5];
vector<int> idx[N + 5];

int lowbit(int x)
{
    return x & -x;
}

void add(int b[], int x, int y)
{
    for (int i = x; i <= 200000; i += lowbit(i))
    {
        b[i] += y;
    }
}

int sum(int b[], int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
    {
        res += b[i];
    }
    return res;
}

signed main()
{
    //freopen("difficulty.in", "r", stdin);
    //freopen("difficulty.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld%lld%lld", &x[i], &a[i], &b[i]);
        a[i] ++ ;
        b[i] ++ ;
        idx[a[i]].push_back(i);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (x[i] == 3)
        {
            cnt ++ ;
        }
        else if (x[i] == 2)
        {
            add(t2, b[i], 1);
        }
        else if (x[i] == 1)
        {
            add(t1, b[i], 1);
        }
    }
    int ans = 1e9;
    for (int i = 100001; i >= 0; i -- )
    {
        for (int w : idx[i])
        {
            if (x[w] == 2)
            {
                cnt ++ ;
                add(t2, b[w], -1);
            }
            else if (x[w] == 1)
            {
                add(t1, b[w], -1);
                add(t2, b[w], 1);
            }
            else if (x[w] == 0)
            {
                add(t1, b[w], 1);
            }
        }
        int l = 0, r = M;
        while (l < r)
        {
            int mid = l + r + 1 >> 1, tmp = cnt + sum(t2, M) + sum(t1, M) - sum(t1, mid - 1);
            if (tmp >= m)
            {
                l = mid;
            }
            else
            {
                r = mid - 1;
            }
        }
        if (l == 0) continue;
        int tmp = cnt + sum(t2, M) - sum(t2, l - 1);
        ans = min(ans, tmp);
    }
    printf("%lld\n", ans);

    return 0;
}
0