Submission #598970

#	Time	Username	Problem	Language	Result	Execution time	Memory
598970		ignus	Snowball (JOI21_ho_t2)	C++14	100 / 100	261 ms	14844 KiB

Main

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

int main(){
	long long n, q;
	cin >> n >> q;
	vector<long long> a;
	for(long long i = 0; i < n; i++){
		long long t;
		cin >> t;
		a.push_back(t);
	}
	vector<long long> l={0};
	vector<long long> r={0};
	long long ll=-10, lr=-10, loc = 0, l1=0, r1=0;
	long long f = -1;
	for(long long i = 0; i < q; i++){
		long long t = 0;
		cin >> t;
		loc+=t;
		if(loc<l1){
			if(f==-1) f=0;
			l1=loc;
			if(ll>lr){
				l[l.size()-1]=loc;
			}else{
				l.push_back(loc);
			}
			ll=i;
		}
		if(loc>r1){
			if(f==-1) f=1;
			r1=loc;
			if(ll<lr){
				r[r.size()-1]=loc;
			}else{
				r.push_back(loc);
			}
			lr=i;
		}
	}
/*	for(long long i = 0; i < l.size(); i++){
		cout << l[i] << ' ';
	}
	cout << "\n\n";
	for(long long i = 0; i < r.size(); i++){
		cout << r[i] << ' ';
	}
	cout << "\n\n";*/
	long long ls[n], rs[n];
	ls[0]=a[0]+l1;
	rs[n-1]=a[n-1]+r1;
	for(long long i = 0; i < n-1; i++){
		if(a[i+1]-a[i]>r1-l1){
			rs[i]=a[i]+r1;
			ls[i+1]=a[i+1]+l1;
			continue;
		}
		long long lb=0, rb=l.size()+r.size()-1, mid;
		//l[(mid+1-f)/2]
		//r[(mid+f)/2]
		while(lb!=rb-1){
			mid=(lb+rb)/2;
			if(r[(mid+f)/2]-l[(mid+1-f)/2]<a[i+1]-a[i])lb=mid;
			else rb=mid;
		}
		//cout << lb << ' ' << rb << '\n';
		//cout << a[i]+r[(lb+f)/2] << ' ' << a[i+1]+l[(lb+1-f)/2] << "\n\n";
		if((lb+f+1)%2){
			rs[i]=a[i]+r[(lb+f)/2];
			ls[i+1]=a[i]+r[(lb+f)/2];
		}else{
			rs[i]=a[i+1]+l[(lb+1-f)/2];
			ls[i+1]=a[i+1]+l[(lb+1-f)/2];
		}
	}
//	cout << '\n';
	for(long long i = 0; i < n; i++){
		cout <<rs[i]-ls[i] << '\n';
	}
	return 0;
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67