Submission #1170891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170891		akqxolotl	Marathon Race 2 (JOI24_ho_t3)	C++20	7 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p<<" ";cerr<<endl;
#define fi first
#define se second
typedef pair<int,int> pii;
#define pb push_back

/*
5 1000
1 2 3 4 5
1
4 2 2
*/

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,l;cin>>n>>l;
	int a[n];
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	int lr[n],rl[n];
	lr[0]=0,rl[n-1]=0;
	for(int i=1;i<n;i++){
		lr[i]=lr[i-1]+(i+1)*(a[i]-a[i-1]);
	}
	for(int i=n-2;i>=0;i--){
		rl[i]=rl[i+1]+(n-i)*(a[i+1]-a[i]);
	}
	
	//debugl(rl)
	
	int qn;cin>>qn;
	for(int q=0;q<qn;q++){
		int s,e,t;cin>>s>>e>>t;
		int ct=n;
		if(s<=e){//start left of end
		
			auto itlbe=lower_bound(a,a+n,e);
			if(itlbe==a+n){//everything is to the left
				ct+=abs(s-a[0]);
				ct+=lr[n-1];
				//debug(ct)
				ct+=(e-a[n-1])*(n+1);
				
				//debug(ct)debug(1)
				
				if(ct<=t)cout<<"Yes\n";
				else cout<<"No\n";
				continue;
			}
			int cp=s;
			int lbe=-1;
			//at a[lbe] youd have taken lbe+1 balls
			if(itlbe!=a){//there is stuff left of e
				lbe=(itlbe-a)-1;
				ct+=lr[lbe];
				ct+=abs(s-a[0]);
				cp=a[lbe];
			}
			ct+=(lbe+2)*(a[n-1]-cp);//run to far right ball - Validated
			//debug((lbe+2)*(a[n-1]-cp))
			int lae=itlbe-a;
			ct+=(lbe+1)*(a[n-1]-a[lae]);//for running back extra
			//debug(ct)
			cp=a[n-1];
			ct+=rl[lae];
			//debug(rl[lae]);
			ct+=(n+1)*(a[lae]-e);//final run
			
			//debug(ct)debug(2)
			
			if(ct<=t)cout<<"Yes\n";
			else cout<<"No\n";
		
		}else{
			auto itlbe=upper_bound(a,a+n,e);//last thing to take before cross
			
			int cp=s;
			int lbe=-1;
			
			if(itlbe==a){//everything is to the right of e
				ct+=abs(s-a[n-1]);
				ct+=rl[0];
				ct+=(n+1)*(abs(e-a[0]));
				//debug(ct)debug(3)
				if(ct<=t)cout<<"Yes\n";
				else cout<<"No\n";
				continue;
			}
			
			if(itlbe!=a+n){//there is stuff to the right of e
				lbe=itlbe-a;
				ct+=rl[lbe]; //Validated
				//debug(rl[lbe]);
				ct+=abs(s-a[n-1]);//Validated - time to run to right
				//debug(abs(s-a[n-1]));
				cp=a[lbe];
				//debug(cp)
			}
			ct+=(lbe+2)*(cp-a[0]);//run to far left ball - Validated
			//debug((lbe+2)*(cp-a[0]))
			
			
			int lae=lbe-1;
			//debug(lbe)
			ct+=(lbe+1)*(a[lae]-a[0]);//for running back extra
			//debug((lbe+2)*(a[lae]-a[0]))
			cp=a[0];
			ct+=lr[lae];
			//debug(lr[lae])
			ct+=(n+1)*(e-a[lae]);//final run
			//debug((n+1)*(e-a[lae]));
			//debug(ct)debug(4)
			
			if(ct<=t)cout<<"Yes\n";
			else cout<<"No\n";
		}
			
	}
}
	

• Subtask 1: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 28
• Subtask 5: 0 / 10
• Subtask 6: 0 / 19
• Subtask 7: 0 / 19