Submission #988471

#	Time	Username	Problem	Language	Result	Execution time	Memory
988471		amirhoseinfar1385	Tower (JOI24_tower)	C++17	100 / 100	825 ms	86820 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
long long n,q,d,a,b,allq[maxn],inf=1e12+2;
pair<long long,long long>mishe[maxn];
vector<pair<long long,long long>>all;
vector<long long>extreme;
map<long long,long long>res,lnk,res2;
vector<pair<long long,long long>>allt;

long long cal(long long w){
	long long p=lower_bound(all.begin(),all.end(),make_pair(w,-1ll))-all.begin();
	p--;
	return res2[mishe[p].first]+(w-mishe[p].first)*a;
}

bool isi(long long w){
	long long p=lower_bound(all.begin(),all.end(),make_pair(w,-1ll))-all.begin();
	p--;
	if(w>=mishe[p].first&&w<=mishe[p].second){
	//cout<<w<<" magemishe "<<endl;
		return 1;
	}
	return 0;
}

void vorod(){
	cin>>n>>q;
	cin>>d>>a>>b;
//	if(a*d<b){
//		assert(0);
//	}
	all.resize(n+2);
	all[0]=make_pair(-1,-1);
	for(long long i=1;i<=n;i++){
		cin>>all[i].first>>all[i].second;
		extreme.push_back(all[i].first+d-1);
	}
	all[n+1].first=all[n+1].second=inf;
	for(long long i=1;i<=q;i++){
		cin>>allq[i];
		extreme.push_back(allq[i]);
	}
	all[n+1].first=inf;
}

void pre(){
	mishe[0]=make_pair(0,all[1].first-1);
	long long l=0;
	for(long long i=1;i<=n;i++){
		while(l<i){
			if(mishe[l].first==inf){
				l++;
				continue;
			}
			if(mishe[l].second+d<=all[i].second){
				l++;
				continue;
			}
			break;
		}
		if(l==i||mishe[l].first+d>=all[i+1].first){
			mishe[i]=make_pair(inf,inf);
			allt.push_back(make_pair(all[i].first,all[i+1].first-1));
			continue;
		}
		mishe[i].second=all[i+1].first-1;
		mishe[i].first=max(all[i].second+1,mishe[l].first+d);
		allt.push_back(make_pair(all[i].first,mishe[i].first-1));
	}
	sort(extreme.begin(),extreme.end());
	extreme.resize(unique(extreme.begin(),extreme.end())-extreme.begin());
	l=(allt.size()-1);
	set<pair<long long ,long long>>st;
	for(long long i=(long long)extreme.size()-1;i>=0;i--){
		while(l>=0&&allt[l].first>extreme[i]){
			long long fl=allt[l].first%d,fr;
			if(allt[l].second-allt[l].first+1>=d){
				st.clear();
				l--;
				continue;
			}
			if(allt[l].second/d==allt[l].first/d){
				fr=allt[l].second%d;
				while((long long)st.size()>0&&(*st.rbegin()).first>=fl){
					auto x=*st.lower_bound(make_pair(fl,-1));
					if(x.first>fr){
						break;
					}
					st.erase(x);
					lnk[x.second]=allt[l].first+d-1;
				}
			}
			else{
				fr=d+1;
				while((long long)st.size()>0&&(*st.rbegin()).first>=fl){
					auto x=*st.lower_bound(make_pair(fl,-1));
					if(x.first>fr){
						break;
					}
					st.erase(x);
					lnk[x.second]=allt[l].first+d-1;
				}
				fl=0;
				fr=allt[l].second%d;
				while((long long)st.size()>0&&(*st.rbegin()).first>=fl){
					auto x=*st.lower_bound(make_pair(fl,-1));
					if(x.first>fr){
						break;
					}
					st.erase(x);
					lnk[x.second]=allt[l].first+d-1;
				}
			}
			l--;
		}
		st.insert(make_pair(extreme[i]%d,extreme[i]));
//		if(l>=0){
//			lnk[extreme[i]]=allt[l].first+d-1;
//		}
	}
		while(l>=0){
			long long fl=allt[l].first%d,fr;
			if(allt[l].second-allt[l].first+1>=d){
				st.clear();
				l--;
				continue;
			}
			if(allt[l].second/d==allt[l].first/d){
				fr=allt[l].second%d;
				while((long long)st.size()>0&&(*st.rbegin()).first>=fl){
					auto x=*st.lower_bound(make_pair(fl,-1));
					if(x.first>fr){
						break;
					}
					st.erase(x);
					lnk[x.second]=allt[l].first+d-1;
				}
			}
			else{
				fr=d+1;
				while((long long)st.size()>0&&(*st.rbegin()).first>=fl){
					auto x=*st.lower_bound(make_pair(fl,-1));
					if(x.first>fr){
						break;
					}
					st.erase(x);
					lnk[x.second]=allt[l].first+d-1;
				}
				fl=0;
				fr=allt[l].second%d;
				while((long long)st.size()>0&&(*st.rbegin()).first>=fl){
					auto x=*st.lower_bound(make_pair(fl,-1));
					if(x.first>fr){
						break;
					}
					st.erase(x);
					lnk[x.second]=allt[l].first+d-1;
				}
			}
			l--;
		}	
	for(long long i=0;i<(long long)extreme.size();i++){
		if(isi(extreme[i])==0){
			res[extreme[i]]=-1;
			continue;
		}
		if(res.count(extreme[i])==0){
			if(lnk.count(extreme[i])==0){
				res[extreme[i]]=(extreme[i]/d)*b+(extreme[i]%d)*a;
				continue;
			}
			long long u=extreme[i],v=lnk[u];
			long long fake=(u-v)/d;
			long long z=(u-v)-fake*d;
			fake*=b;
			fake+=a*(z);
			//cout<<u<<" "<<v<<" "<<fake<<" "<<z<<endl;
			res[u]=res[v]+fake;
			if(u<=v){
				assert(0);
			}
		}
	}
	for(long long i=1;i<=n;i++){
		if(mishe[i].first!=inf){
			res2[mishe[i].first]=b+cal(mishe[i].first-d);
		}
	}
}

void solve(){
	for(long long i=1;i<=q;i++){
		if(isi(allq[i])){
			if(a*d<b){
				cout<<cal(allq[i])<<"\n";
				continue;
			}
			long long mainres=res[allq[i]];
			cout<<mainres<<"\n";
			continue;
		}
		cout<<-1<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 38 / 38
• Subtask 3: 25 / 25
• Subtask 4: 32 / 32