結果

問題 No.568 じゃんじゃん　落とす　委員会
ユーザー vjudge1
提出日時 2025-05-26 20:43:35
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,092 bytes
コンパイル時間 4,197 ms
コンパイル使用メモリ 276,644 KB
実行使用メモリ 17,364 KB
最終ジャッジ日時 2025-05-26 20:43:44
合計ジャッジ時間 7,507 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,c1,c2,c3,ans=0x3f3f3f3f,x[N],a[N],b[N];
vector<int>bul[N];
struct BIT
{
	int c[N];
	void update(int u,int w){u++;for(int i=u;i<N;i+=i&-i)c[i]+=w;}
	int query(int u){u++;int r=0;for(int i=u;i;i-=i&-i)r+=c[i];return r;}
}tr1,tr2;
int main()
{
//	freopen("difficulty.in","r",stdin);
//	freopen("difficulty.out","w",stdout);
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>a[i]>>b[i];
		if(x[i]==3){c3++;i--;n--;}
		if(x[i]==2){c2++;tr2.update(b[i],1);bul[a[i]].push_back(i);}
		if(x[i]==1){c1++;tr1.update(b[i],1);bul[a[i]].push_back(i);}
		if(x[i]==0)bul[a[i]].push_back(i);
	}
	for(int i=100001,r,c;~i;i--)
	{
		for(int p:bul[i])
		{
			if(x[p]==2){c2--;tr2.update(b[p],-1);c3++;}
			if(x[p]==1){c1--;tr1.update(b[p],-1);c2++;tr2.update(b[p],1);}
			if(x[p]==0){c1++;tr1.update(b[p],1);}
		}
		r=max(0,m-c2-c3);
		if(r<=c1)
		{
			c=262143;
			for(int j=17;~j;j--)if(c1-tr1.query(c-(1<<j)-1)<r)c-=(1<<j);
			ans=min(ans,c3+c2-tr2.query(c-1));
		}
	}
	cout<<ans;
}
0