Submission #697362

#	Time	Username	Problem	Language	Result	Execution time	Memory
697362		micjan	Snowball (JOI21_ho_t2)	C++14	100 / 100	105 ms	15440 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define st first
#define nd second
#define FOR(i,j,k) for(auto i = (j); i<(k); i++)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define pb push_back
#define BOOST ios_base::sync_with_stdio(0);cin.tie(0);

const int MN = 2e5+10;
const ll inf = 1e18+2;

ll maxi[MN], mini[MN];
ll poz[MN];
ll W[MN];

ll ans[MN];//jak dużo zjadła kulka

int main()
{
	BOOST;
	int n,q;
	cin>>n>>q;
	FOR(i,1,n+1) cin>>poz[i];
	ll sum = 0;
	FOR(i,1,q+1)
	{
		cin>>W[i];
		sum+=W[i];
		maxi[i] = max(maxi[i-1],sum);
		mini[i] = min(mini[i-1],sum);
	}

	ans[1] += abs(mini[q]);//weźmie wszystko po lewej
	ans[n] += maxi[q];//weźmie wszystko po prawej
	FOR(i,2,n+1)//punkt spotkania i oraz i-1 kulki
	{
		int l = 0, p = q;
		while(l<p)
		{
			int s = (l+p+1)>>1;
			if(poz[i-1]+maxi[s] <= poz[i]+mini[s])
				l = s;
			else
				p = s-1;
		}
		ans[i-1]+=maxi[l];
		ans[i]+= -mini[l];
		if(l<q)
			ans[ W[l+1] < 0 ? i : i-1 ] += poz[i]+mini[l]-poz[i-1]-maxi[l];
	}
	FOR(i,1,n+1) cout<<ans[i]<<"\n";
}

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