Submission #1612434

---

Source Code Expand

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<iomanip>
//<< setprecision(5)
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define dme cout<<-1<<endl;return 0
const int mod=1000000007;
const llint big=1e18+10;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
int main(void){
	llint n,A,B;cin>>n>>A>>B;
	deque<pair<llint,llint>>aset;//数字,個数 一番近いのをAに入れた
	//int apot=0;//sumにどこまで加算されたか
	deque<pair<llint,llint>>bset;//一番近いのをBに入れた
	//int bpot=0;//sumにどこまで加算されたか
	llint asum=0,bsum=0;
	aset.pub(mp(-big,1));
	bset.pub(mp(-big,1));
	llint mae=-big;//前の数字
	for(int i=0;i<=n;i++){
		llint s;if(i<n){cin>>s;}else{s=big+big;}
		while(!bset.empty()&&bset.front().fir+A<=s){
			bsum+=bset.front().sec;bset.pof();
		}
		while(!aset.empty()&&aset.front().fir+B<=s){
			asum+=aset.front().sec;aset.pof();
		}
		asum%=mod;
		bsum%=mod;
		aset.pub(mp(mae,bsum));
		bset.pub(mp(mae,asum)); 
		/*
		cout<<"de"<<asum<<"naka";
		for(auto it:aset){cout<<" "<<it.sec;}cout<<endl;
		cout<<"de"<<bsum<<"naka";
		for(auto it:bset){cout<<" "<<it.sec;}cout<<endl;*/
		if(s-mae<A){
			while(aset.size()>1){
				aset.pof();
			}asum=0;
		}
		if(s-mae<B){
			while(bset.size()>1){
				bset.pof();
			}bsum=0;
		}
		mae=s;
	}
	llint ans=aset.back().sec+bset.back().sec;
	if(ans%2==1){ans+=mod;}
	ans/=2;
	ans%=mod;
	cout<<ans<<endl;
}

Submission Info

Judge Result