結果

問題 No.568 じゃんじゃん　落とす　委員会
ユーザー vjudge1
提出日時 2025-05-17 17:55:23
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 50 ms / 1,000 ms
コード長 3,206 bytes
コンパイル時間 6,400 ms
コンパイル使用メモリ 214,544 KB
実行使用メモリ 22,504 KB
最終ジャッジ日時 2025-05-17 17:55:31
合計ジャッジ時間 6,793 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
??????
??????
??????
??????
D P ????
??????
??????
??????
??????
??? l l?
??????
??????
?? OI ??
??????
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define eps 1e-9
//#define ENF 1e13
inline int read()
{
   int x=0,f=1;char ch=getchar();
   while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
   while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
   return x*f;
}
void write(int x)
{
   if(x<0)putchar('-'),x=-x;
   if(x<10)putchar(x+'0');
   else write(x/10),putchar(x%10+'0');
}
const int N=3e6;
const int mod=1e9+7;
int n,m;
int T[N];
struct node{
	int x,a,b,id;
}t[N];
int top;
int ans; 
bool cmp(node x,node y){
	return x.a>y.a;
}
bool ccmp(node x,node y){
	return x.b>y.b;
}
node tt[N];
struct ns{
	int two,three;	
}sum[N];
struct tree{
	int t[N];
	int lowbit(int x){
		return x&(-x);
	}
	void up(int x,int k){
		while(x<=100002){
			t[x]+=k;
			x+=lowbit(x);
		}
		return;
	}
	int qry(int x){
		int ret=0;
		while(x){
			ret+=t[x];
			x-=lowbit(x);
		}
		return ret;
	}
}; 
tree z,zz; 
bool check(int x){
	if(x==0)return z.qry(100002)-z.qry(0)>=m;
	if(z.qry(100002)-z.qry(x-1)>=m)return 1;
	return 0;
}
signed main(){
//	freopen("difficulty.in","r",stdin);
//	freopen("difficulty.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		int d=read(),a=read()+1,b=read()+1;
		if(d>=3){
			ans++;
			m--;
			continue;
		}
		if(d>=2)m--;
		top++;
		t[top]={d,a,b,top};
		tt[top]=t[top];
		T[top]=d;
	}
	sort(t+1,t+1+top,cmp);
	sort(tt+1,tt+1+top,ccmp);
	int sum0=0,sum1=0;
	int sm=INT_MAX;
   	int r=0;
   	int U=0;
   	for(int i=1;i<=top;i++){
   		if(tt[i].x==1) z.up(tt[i].b,1);
   		if(tt[i].x==2) zz.up(tt[i].b,1);
	}
	int op=0;
	int i=0;
	int L=0;
	int R=100002;
	int As=-1;
	while(L<=R){
   		int mid=(L+R)>>1;
		if(check(mid))L=mid+1,As=mid;
		else R=mid-1;	
	} 
	if(m<=0){
		cout<<ans<<"\n";
		return 0;
	}
	if(As>0)sm=min(sm,op+zz.qry(100002)-zz.qry(As-1));
	if(As==0)sm=min(sm,op+zz.qry(100002));
	while(i<=top){
		i++;
		if(i>top)break;
   		while(t[i].a==t[i+1].a){
			if(m<=0){
				sm=min(sm,op);
				break;
			}
			T[t[i].id]++;
   			op+=(T[t[i].id]==3);
			if(T[t[i].id]==3) zz.up(t[i].b,-1);	
			if(T[t[i].id]==2) zz.up(t[i].b,1),z.up(t[i].b,-1),m--;
   			if(T[t[i].id]==1) z.up(t[i].b,1);
   			i++;
   		}
   		if(m<=0)break;
  	 	T[t[i].id]++;
  	 	op+=(T[t[i].id]==3);
		if(T[t[i].id]==3) zz.up(t[i].b,-1);	
		if(T[t[i].id]==2) zz.up(t[i].b,1),z.up(t[i].b,-1),m--;
   		if(T[t[i].id]==1) z.up(t[i].b,1);
   		if(m<=0){
   			sm=min(sm,op);
   			break;
		}
		int l=0;
   		int r=100002;
   		int as=-1;
   		while(l<=r){
   			int mid=(l+r)>>1;
			if(check(mid))l=mid+1,as=mid;
			else r=mid-1;	
		}
		if(as>=0){
			if(as==0){
				sm=min(sm,op+zz.qry(100002));
				continue;
			}
			sm=min(sm,op+zz.qry(100002)-zz.qry(as-1));
		}
	}
	cout<<ans+(sm==INT_MAX?0:sm)<<"\n";
   return 0;
}
// ?????????????AC????
// ?????????????????????????
// ??????????????????
// ????????????????????????????????????
// ???????????????????????????????
// ????????????
// ????????????
// ????????????
// ????????????????????
// ????????????????????
// ????????????????????????????????
// ???????????????????????
// ???????????
// ?????????????
0