結果

問題 No.568 じゃんじゃん　落とす　委員会
ユーザー ryoissyryoissy
提出日時 2017-09-08 23:05:59
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,464 bytes
コンパイル時間 1,640 ms
コンパイル使用メモリ 162,444 KB
実行使用メモリ 8,960 KB
最終ジャッジ日時 2024-04-24 20:56:44
合計ジャッジ時間 5,593 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 51 ms
8,832 KB
testcase_01 AC 49 ms
8,704 KB
testcase_02 AC 111 ms
7,808 KB
testcase_03 AC 105 ms
7,680 KB
testcase_04 AC 107 ms
7,552 KB
testcase_05 AC 5 ms
7,808 KB
testcase_06 AC 106 ms
7,552 KB
testcase_07 AC 113 ms
7,680 KB
testcase_08 WA -
testcase_09 AC 5 ms
7,552 KB
testcase_10 AC 5 ms
7,552 KB
testcase_11 AC 112 ms
7,680 KB
testcase_12 AC 48 ms
8,832 KB
testcase_13 AC 122 ms
8,960 KB
testcase_14 AC 108 ms
8,704 KB
testcase_15 WA -
testcase_16 AC 94 ms
8,704 KB
testcase_17 AC 45 ms
8,832 KB
testcase_18 AC 107 ms
8,832 KB
testcase_19 AC 110 ms
8,832 KB
testcase_20 AC 60 ms
8,704 KB
testcase_21 AC 138 ms
8,960 KB
testcase_22 AC 51 ms
8,704 KB
testcase_23 AC 107 ms
7,680 KB
testcase_24 AC 5 ms
7,808 KB
testcase_25 AC 5 ms
7,680 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:51:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   51 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
main.cpp:53:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   53 |                 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[100005];

int n,m;
int x[100001],a[100001],b[100001];


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;
			}
			res=min(res,seg[3].query(0,n_)+seg[2].query(l,n_));
		}
	}
	printf("%d\n",res);
	return 0;
}
0