Submission #941725

#	Time	Username	Problem	Language	Result	Execution time	Memory
941725		Litusiano	Snowball (JOI21_ho_t2)	C++17	100 / 100	524 ms	17648 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int inf = 1e18;
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,q; cin>>n>>q;
	vector<int> v(n); for(int& i : v) cin>>i;
	vector<int> mn(q+1,0), mx(q+1,0);
	int act = 0;
	int cnt = 0;
	vector<int> queries = {0};
	for(int _ = 0; _<q; _++){
		cnt++;
		int w; cin>>w;
		act+=w;
		queries.push_back(w);
		mn[cnt] = min(mn[cnt-1],act);
		mx[cnt] = max(mx[cnt-1],act);
	}
	vector<pair<int,int>> intervals(n);
	for(int i = 0; i<n-1; i++){
		// intersection between dif
		int dif = v[i+1] - v[i];
		int l = 0; int r = q+1;
		while(r > l+1){
			int m = (l+r)/2;
			if(abs(mn[m]) + mx[m] >= dif) r = m;
			else l = m;
		}
		cerr<<r<<" "; 
		if(r == q+1){
			intervals[i].second = mx[q];
			intervals[i+1].first = mn[q];
		}
		else{
			// intersects here
			if(queries[r] > 0){
				// mn rules
				intervals[i+1].first = mn[r];
				intervals[i].second = v[i+1] + mn[r] - v[i];
			}
			else{
				intervals[i].second = mx[r];
				intervals[i+1].first = -(v[i+1] - (v[i] + mx[r])); 
			}
		}
	}
	// cerr<<"END R"<<endl;
	intervals[0].first = mn[q];
	intervals[n-1].second = mx[q];
	for(auto x : intervals){
		// cout<<x.first<<" "<<x.second<<" ";
		cout<<x.second - x.first<<endl;
	}
}

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