提出 #72363932

ソースコード 拡げる

#include<cstdio>
#include<algorithm>
#define M 300005
using namespace std;
int A[M]; 
int n,q;
int Solve(int a,int b){
	int id=lower_bound(A+1,A+n+1,a)-A; 
//	printf("[id]=%d\n",id);
	if(b<=A[id]-a)return a+b-1;
	b-=A[id]-a;
//	printf("[%d %d]\n",a,b);
	int L=id,R=n,res=id;
	while(L<=R){
		int mid=(L+R)>>1;
		int tmp=A[mid]-A[id]+1-(mid-id+1);
		if(tmp<b){
			res=mid;
			L=mid+1;
		}else R=mid-1;
	}
//	printf("res=%d\n",res);
	return A[id]+b+(res-id);
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
	A[++n]=2e9+3;
	sort(A+1,A+n+1);
	for(int i=1;i<=q;i++){
		int a,b;
		scanf("%d%d",&a,&b); 
		printf("%d\n",Solve(a,b)); 
	}
	return 0;
}

提出情報

提出日時
問題 D - Forbidden List 2
ユーザ Hacker_
言語 C++23 (GCC 15.2.0)
得点 400
コード長 705 Byte
結果 AC
実行時間 155 ms
メモリ 4508 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 2
AC × 22
セット名 テストケース
Sample 00-sample-01.txt, 00-sample-02.txt
All 00-sample-01.txt, 00-sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt
ケース名 結果 実行時間 メモリ
00-sample-01.txt AC 1 ms 1668 KiB
00-sample-02.txt AC 1 ms 1628 KiB
01-01.txt AC 2 ms 1468 KiB
01-02.txt AC 3 ms 1544 KiB
01-03.txt AC 3 ms 1620 KiB
01-04.txt AC 3 ms 1448 KiB
01-05.txt AC 2 ms 1664 KiB
01-06.txt AC 2 ms 1712 KiB
01-07.txt AC 2 ms 1676 KiB
01-08.txt AC 2 ms 1620 KiB
01-09.txt AC 2 ms 1520 KiB
01-10.txt AC 2 ms 1620 KiB
01-11.txt AC 2 ms 1656 KiB
01-12.txt AC 2 ms 1524 KiB
01-13.txt AC 104 ms 3292 KiB
01-14.txt AC 137 ms 4464 KiB
01-15.txt AC 155 ms 4480 KiB
01-16.txt AC 59 ms 2996 KiB
01-17.txt AC 144 ms 4268 KiB
01-18.txt AC 108 ms 3288 KiB
01-19.txt AC 103 ms 4508 KiB
01-20.txt AC 106 ms 3264 KiB