Submission #73101179

Source Code Expand

#include<set>
#include<queue>
#include<string> 
#include<iostream>
#include<algorithm>
using namespace std;

int n,d;
int a[400005];
long long ans;
set<int>se;

int main(){
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int l=1,r=1;
	for( ;r<=n;r++){
		while(true){
			auto near=se.lower_bound(a[r]-d+1);
			if(near!=se.end()&&*near<=a[r]+d-1){
				se.erase(a[l]);
				l++;
			}
			else break;
		}
		se.insert(a[r]);
		ans+=(r-l+1);
	}
	cout<<ans<<endl;
	
	return 0;
}

Submission Info

Submission Time
Task E - Sparse Range
User zgmbsydmz
Language C++23 (GCC 15.2.0)
Score 450
Code Size 507 Byte
Status AC
Exec Time 441 ms
Memory 24008 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 3
AC × 21
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All min1.txt, min2.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
min1.txt AC 1 ms 3408 KiB
min2.txt AC 1 ms 3360 KiB
random_01.txt AC 258 ms 9772 KiB
random_02.txt AC 232 ms 8768 KiB
random_03.txt AC 255 ms 9124 KiB
random_04.txt AC 218 ms 8424 KiB
random_05.txt AC 188 ms 5224 KiB
random_06.txt AC 107 ms 4396 KiB
random_07.txt AC 175 ms 5156 KiB
random_08.txt AC 129 ms 4712 KiB
random_09.txt AC 174 ms 5156 KiB
random_10.txt AC 115 ms 4560 KiB
random_11.txt AC 204 ms 8868 KiB
random_12.txt AC 24 ms 3884 KiB
random_13.txt AC 107 ms 4892 KiB
random_14.txt AC 305 ms 24008 KiB
random_15.txt AC 441 ms 23708 KiB
random_16.txt AC 319 ms 23876 KiB
sample_01.txt AC 1 ms 3572 KiB
sample_02.txt AC 1 ms 3400 KiB
sample_03.txt AC 1 ms 3560 KiB