結果
問題 | No.568 じゃんじゃん 落とす 委員会 |
ユーザー | rpy3cpp |
提出日時 | 2017-09-09 15:17:08 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 96 ms / 1,000 ms |
コード長 | 2,586 bytes |
コンパイル時間 | 1,914 ms |
コンパイル使用メモリ | 179,888 KB |
実行使用メモリ | 16,100 KB |
最終ジャッジ日時 | 2023-08-20 09:48:21 |
合計ジャッジ時間 | 4,440 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 27 ms
5,880 KB |
testcase_01 | AC | 27 ms
5,928 KB |
testcase_02 | AC | 33 ms
12,472 KB |
testcase_03 | AC | 33 ms
12,736 KB |
testcase_04 | AC | 31 ms
12,696 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 31 ms
12,388 KB |
testcase_07 | AC | 34 ms
12,432 KB |
testcase_08 | AC | 15 ms
12,580 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 34 ms
12,476 KB |
testcase_12 | AC | 27 ms
5,944 KB |
testcase_13 | AC | 96 ms
15,820 KB |
testcase_14 | AC | 87 ms
15,808 KB |
testcase_15 | AC | 96 ms
15,924 KB |
testcase_16 | AC | 76 ms
15,668 KB |
testcase_17 | AC | 25 ms
5,756 KB |
testcase_18 | AC | 78 ms
15,760 KB |
testcase_19 | AC | 83 ms
16,100 KB |
testcase_20 | AC | 66 ms
15,860 KB |
testcase_21 | AC | 86 ms
15,672 KB |
testcase_22 | AC | 27 ms
5,920 KB |
testcase_23 | AC | 31 ms
12,500 KB |
testcase_24 | AC | 2 ms
4,376 KB |
testcase_25 | AC | 2 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using T = int; struct XAB{ int x; int a; int b; XAB(int _x=0, int _a=0, int _b=0):x(_x), a(_a), b(_b){} }; struct BIT{ vector<T> bit; BIT(int n) : bit(n, 0){} T sum(int j) const { assert(j < (int)bit.size()); T s = 0; for (; j >= 0; j = (j & (j + 1)) - 1) s += bit[j]; return s; } T total() const { return sum(bit.size() - 1);} T count_larger(int k) const { return total() - sum(k - 1);} void add(int k, T a) {for (; k < bit.size(); k |= k + 1) bit[k] += a;} }; vector<XAB> ignore_3complete(const vector<XAB> & xabs){ vector<XAB> result; for (auto xab : xabs){ if (xab.x != 3) result.emplace_back(xab); } return result; } int count_2complete(const vector<XAB> & xabs){ int c = 0; for (auto &xab : xabs) if (xab.x == 2) ++c; return c; } int count3(const vector<BIT> & B, int M){ int solved0 = B[0].total(); int solved1 = B[1].total(); int solved2 = B[2].total(); int solved3 = B[3].total(); int target = M - solved2 - solved3; if (target <= 0) return solved3; if (target > solved1) return 1e9; int OK = 0; int NG = 100001; while (NG > (OK + 1)){ int mid = (OK + NG)/2; if (B[1].count_larger(mid) >= target){ OK = mid; }else{ NG = mid; } } return solved3 + B[2].count_larger(OK); } void update_B(const vector<vector<vector<int>>> & data, vector<BIT> & B, int SA){ for (int i = 2; i >= 0; --i){ for (auto b : data[i][SA]){ B[i + 1].add(b, -1); B[i].add(b, 1); } } } int solve(vector<XAB> & xabs, int M){ if (M <= 0) return 0; int n_2complete = count_2complete(xabs); if (n_2complete >= M) return 0; vector<vector<vector<int>>> data(3, vector<vector<int>>(100005)); vector<BIT> B(4, BIT(100002)); for (auto &xab : xabs){ data[xab.x][xab.a].push_back(xab.b); B[xab.x + 1].add(xab.b, 1); } int record = 1e9; for (int SA = 0; SA <= 100001; ++SA){ int score = count3(B, M); record = min(record, score); update_B(data, B, SA); } return record; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector<XAB> xabs(N); for (auto & xab : xabs) cin >> xab.x >> xab.a >> xab.b; auto xabs012 = ignore_3complete(xabs); int n_3complete = N - xabs012.size(); cout << solve(xabs012, M - n_3complete) + n_3complete << endl; return 0; }