Submission #380234

#	Time	Username	Problem	Language	Result	Execution time	Memory
380234		peijar	Snowball (JOI21_ho_t2)	C++17	100 / 100	1304 ms	17004 KiB

Main

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

const int INF = 1e18;

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int nbBonhommes, nbNeiges;
	cin >> nbBonhommes >> nbNeiges;
	vector<int> posBonhommes(nbBonhommes);
	for (auto &v : posBonhommes) cin >> v;

	vector<int> quantiteNeige(nbNeiges);
	for (auto &v : quantiteNeige)
		cin >> v;

	vector<int> cumulNeige(nbNeiges+1);
	vector<int> maxNeige(nbNeiges+1);
	vector<int> minNeige(nbNeiges+1);
	for (int iNeige = 0; iNeige < nbNeiges; ++iNeige) 
	{
		cumulNeige[iNeige+1] = cumulNeige[iNeige] + quantiteNeige[iNeige];
		minNeige[iNeige+1] = min(minNeige[iNeige], cumulNeige[iNeige+1]);
		maxNeige[iNeige+1] = max(maxNeige[iNeige], cumulNeige[iNeige+1]);
	}

	vector<int> tailleFinale(nbBonhommes);
	for (int iBonhomme(0); iBonhomme < nbBonhommes; ++iBonhomme)
	{
		int extremGauche(INF), extremDroite(INF);
		// A gauche ? 
		if (!iBonhomme)
			extremGauche = min(posBonhommes[iBonhomme], posBonhommes[iBonhomme] + minNeige[nbNeiges]);
		else
		{
			int lo(posBonhommes[iBonhomme-1]), up(posBonhommes[iBonhomme]);
			while (lo < up)
			{
				int mid = lo + (up - lo) / 2;
				if (minNeige[nbNeiges] + posBonhommes[iBonhomme] > mid)
				{
					lo = mid+1;
					continue;
				}
				int loBis(0), upBis(nbNeiges);
				while (loBis < upBis)
				{
					int midBis = (loBis + upBis) / 2;
					if (minNeige[midBis] + posBonhommes[iBonhomme] > mid)
						loBis = midBis + 1;
					else
						upBis = midBis;
				}
				int premierDepassement = loBis;
				if (premierDepassement and maxNeige[premierDepassement-1] + posBonhommes[iBonhomme-1] >= mid+1)
				{
					lo = mid+1;
					continue;
				}
				if (posBonhommes[iBonhomme-1] + cumulNeige[premierDepassement] >= mid + 1 
						and mid+1 - (posBonhommes[iBonhomme-1] + cumulNeige[premierDepassement-1]) < (posBonhommes[iBonhomme] + cumulNeige[premierDepassement-1]) - mid)
					lo = mid+1;
				else
					up = mid;
			}
			extremGauche = lo;
		}
		if (iBonhomme == nbBonhommes-1)
			extremDroite = max(posBonhommes[iBonhomme], posBonhommes[iBonhomme] + maxNeige[nbNeiges]);
		else
		{
			int lo(posBonhommes[iBonhomme]), up(posBonhommes[iBonhomme+1]);
			while (lo < up)
			{
				int mid = lo + (up - lo + 1) / 2;
				if (maxNeige[nbNeiges] + posBonhommes[iBonhomme] < mid)
				{
					up = mid-1;
					continue;
				}
				int premierDepassement = 
					lower_bound(maxNeige.begin(), maxNeige.end(), mid - posBonhommes[iBonhomme]) - maxNeige.begin();
				if (premierDepassement and minNeige[premierDepassement-1] + posBonhommes[iBonhomme+1] <= mid-1)
				{
					up = mid-1;
					continue;
				}
				if ( posBonhommes[iBonhomme+1] + cumulNeige[premierDepassement] <= mid - 1 and   posBonhommes[iBonhomme+1] + cumulNeige[premierDepassement-1] - mid -1< mid- (posBonhommes[iBonhomme] + cumulNeige[premierDepassement-1]))
					up = mid-1;
				else
					lo = mid;
			}
			extremDroite = lo;
		}
		tailleFinale[iBonhomme] = extremDroite - extremGauche;	
	}
	for (auto v : tailleFinale)
		cout << v << '\n';
}

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