結果

問題 No.568 じゃんじゃん　落とす　委員会
ユーザー ryoissyryoissy
提出日時 2017-09-08 23:12:55
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 182 ms / 1,000 ms
コード長 1,468 bytes
コンパイル時間 2,342 ms
コンパイル使用メモリ 163,552 KB
実行使用メモリ 10,092 KB
最終ジャッジ日時 2024-05-07 16:17:35
合計ジャッジ時間 5,187 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
9,540 KB
testcase_01 AC 60 ms
9,284 KB
testcase_02 AC 129 ms
9,028 KB
testcase_03 AC 122 ms
9,284 KB
testcase_04 AC 122 ms
8,516 KB
testcase_05 AC 3 ms
7,872 KB
testcase_06 AC 121 ms
8,256 KB
testcase_07 AC 127 ms
8,004 KB
testcase_08 AC 109 ms
8,900 KB
testcase_09 AC 4 ms
8,772 KB
testcase_10 AC 4 ms
7,620 KB
testcase_11 AC 126 ms
7,876 KB
testcase_12 AC 56 ms
9,408 KB
testcase_13 AC 149 ms
9,284 KB
testcase_14 AC 126 ms
9,540 KB
testcase_15 AC 182 ms
10,052 KB
testcase_16 AC 116 ms
9,536 KB
testcase_17 AC 56 ms
9,792 KB
testcase_18 AC 130 ms
10,052 KB
testcase_19 AC 133 ms
9,156 KB
testcase_20 AC 71 ms
10,092 KB
testcase_21 AC 169 ms
10,048 KB
testcase_22 AC 59 ms
10,052 KB
testcase_23 AC 121 ms
8,132 KB
testcase_24 AC 4 ms
8,008 KB
testcase_25 AC 4 ms
8,388 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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