結果

問題 No.568 じゃんじゃん　落とす　委員会
コンテスト
ユーザー ryoissy
提出日時 2017-09-08 23:12:55
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 179 ms / 1,000 ms
コード長 1,468 bytes
コンパイル時間 1,477 ms
コンパイル使用メモリ 162,532 KB
実行使用メモリ 8,960 KB
最終ジャッジ日時 2024-11-30 10:41:29
合計ジャッジ時間 4,962 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:49:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
main.cpp:51:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   51 |                 scanf("%d%d%d",&dat[i].x,&dat[i].a,&dat[i].b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

const int n_=1<<17;

class segtree{
public:
	int dp[1<<18];
	segtree(){
		memset(dp,0,sizeof(dp));
	}
	void update(int k,int v){
		k+=n_-1;
		dp[k]+=v;
		while(k>0){
			k=(k-1)/2;
			dp[k]=dp[k*2+1]+dp[k*2+2];
		}
	}

	int query(int a,int b,int k=0,int l=0,int r=n_){
		if(b<=l || r<=a)return 0;
		if(a<=l && r<=b)return dp[k];
		int mid=(l+r)/2;
		int vl=query(a,b,k*2+1,l,mid);
		int vr=query(a,b,k*2+2,mid,r);
		return vl+vr;
	}
};

segtree seg[4];

struct data{
	int x,a,b;
	data(){}
	bool operator<(const data &d)const{
		return a>d.a;
	}
};

data dat[200005];

int n,m;

int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&dat[i].x,&dat[i].a,&dat[i].b);
		seg[dat[i].x].update(dat[i].b,1);
	}
	sort(dat,dat+n);
	int now=0;
	int res=n;
	for(int i=100001;i>=0;i--){
		while(now<n && dat[now].a==i){
			if(dat[now].x==3){
				now++;
				continue;
			}
			seg[dat[now].x].update(dat[now].b,-1);
			seg[dat[now].x+1].update(dat[now].b,1);
			now++;
		}
		int rest=m-seg[2].query(0,n_)-seg[3].query(0,n_);
		if(rest<=0){
			res=min(res,seg[3].query(0,n_));
		}else{
			int l=0,r=100002;
			while(l+1<r){
				int mid=(l+r)/2;
				if(seg[1].query(mid,n_)>=rest)l=mid;
				else r=mid;
			}
			if(seg[1].query(l,n_)<rest)continue;
			res=min(res,seg[3].query(0,n_)+seg[2].query(l,n_));
		}
	}
	printf("%d\n",res);
	return 0;
}
0