結果
問題 | No.568 じゃんじゃん 落とす 委員会 |
ユーザー |
|
提出日時 | 2017-09-08 23:23:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,149 bytes |
コンパイル時間 | 2,213 ms |
コンパイル使用メモリ | 179,892 KB |
実行使用メモリ | 12,448 KB |
最終ジャッジ日時 | 2024-11-07 06:41:07 |
合計ジャッジ時間 | 5,189 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 WA * 5 |
ソースコード
#include <bits/stdc++.h>#define mp make_pair#define pb push_back#define all(x) (x).begin(),(x).end()#define YES() printf("YES\n")#define NO() printf("NO\n")#define Yes() printf("Yes\n")#define No() printf("No\n")using namespace std;#define int long long//typedef long long ll;typedef vector<bool> vb;typedef vector<int> vi;typedef vector<vb> vvb;typedef vector<vi> vvi;const int INF=1e+9;const double EPS=1e-9;const int MOD=1000000007;const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};class BIT{vector<int> bit;public:BIT(int siz){bit.resize(siz + 1,0);}void add(int i,int x){i++;while(i < bit.size()){bit[i] += x;i += i & -i;}}int sum(int i){i++;int s = 0;while(i){s += bit[i];i -= i & -i;}return s;}};typedef pair<int,int> PP;typedef pair<int,PP> P;signed main(){int n,m,kan2 = 0,kan3 = 0,mi = INF,last[100002];cin >> n >> m;BIT one(n),two(n);vector<P> vec;vector<int> upd[100002];for(int i = 0;i < 100002;i++) last[i] = -1;for(int i = 0;i < n;i++){int x,a,b;cin >> x >> a >> b;vec.push_back(mp(b,mp(x,a)));if(x >= 2) kan2++;if(x >= 3) kan3++;}sort(vec.begin(),vec.end(),greater<P>());for(int i = 0;i < n;i++){upd[vec[i].second.second].push_back(i);if(vec[i].second.first == 1) one.add(i,1);else if(vec[i].second.first == 2) two.add(i,1);last[vec[i].first] = i;}for(int i = 100000;i >= 0;i--) if(last[i] == -1) last[i] = last[i + 1];for(int i = 100001;i >= 0;i--){if(!upd[i].size()) continue;for(int v : upd[i]){if(vec[v].second.first == 0){one.add(v,1);}else if(vec[v].second.first == 1){one.add(v,-1);two.add(v,1);kan2++;}else if(vec[v].second.first == 2){two.add(v,-1);kan3++;}vec[v].second.first++;}int low = -1,up = 100002;while(up - low > 1){int mid = (low + up) / 2;if(kan2 + one.sum(last[mid]) >= m) low = mid;else up = mid;}if(kan2 + one.sum(last[low]) < m) continue;mi = min(mi,kan3 + two.sum(last[low]));}cout << mi << endl;return 0;}