Submission #569205

#	Time	Username	Problem	Language	Result	Execution time	Memory
569205		blue	Fish 2 (JOI22_fish2)	C++17	100 / 100	1028 ms	35728 KiB

fish2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
#define sz(x) int(x.size())

int N;
vll A;

int Q;

struct group
{
	int i; //inclusive of the group, not the barrier.
	ll Asum;
	int winners;
};

struct info
{
	int l;
	int r;

	ll Asum;
	int winners;

	vector<group> pref;
	vector<group> suff;

	info()
	{
		;
	}

	info(int i)
	{
		l = r = i;
		Asum = A[i];
		winners = 1;
	}
};

void combine(info& res, const info& X, const info& Y) //!
{
	// cerr << "combine called\n";
	res.l = X.l;
	res.r = Y.r;

	res.Asum = X.Asum + Y.Asum;
	res.winners = 0;







	int Xs = sz(X.suff);

	ll Xdp[1 + Xs];
	Xdp[0] = A[X.r];
	for(int i = 1; i <= Xs; i++)
		Xdp[i] = max(Xdp[i-1], A[X.suff[i-1].i - 1] - X.suff[i-1].Asum);


	int Ys = sz(Y.pref);

	ll Ydp[1 + Ys];
	Ydp[0] = A[Y.l];
	for(int i = 1; i <= Ys; i++)
		Ydp[i] = max(Ydp[i-1], A[Y.pref[i-1].i + 1] - Y.pref[i-1].Asum);


	// cerr << "#\n";




	int XYreach[1 + Xs];
	int XXreach[1 + Xs];

	int YXreach[1 + Ys];
	int YYreach[1 + Ys];

	int xi, yi;

	yi = Ys;
	for(xi = Xs; xi >= 0; xi--)
	{
		ll currsum = (xi == Xs ? X.Asum : X.suff[xi].Asum);
		while(yi >= 0 && Ydp[yi] > currsum)
			yi--;

		ll Ygain;
		if(yi == Ys)
			Ygain = Y.Asum;
		else if(yi == -1)
			Ygain = 0;
		else
			Ygain = Y.pref[yi].Asum;

		if(xi < Xs && currsum + Ygain >= A[X.suff[xi].i - 1])
		{
			XXreach[xi] = XXreach[xi+1];
			XYreach[xi] = XYreach[xi+1];
		}
		else
		{
			XXreach[xi] = xi;
			XYreach[xi] = yi;
		}
	}
	// cerr << "#2\n";


	xi = Xs;
	for(yi = Ys; yi >= 0; yi--)
	{
		ll currsum = (yi == Ys ? Y.Asum : Y.pref[yi].Asum);
		while(xi >= 0 && Xdp[xi] > currsum)
			xi--;

		ll Xgain;
		if(xi == Xs)
			Xgain = X.Asum;
		else if(xi == -1)
			Xgain = 0;
		else
			Xgain = X.suff[xi].Asum;

		if(yi < Ys && currsum + Xgain >= A[Y.pref[yi].i + 1])
		{
			YYreach[yi] = YYreach[yi+1];
			YXreach[yi] = YXreach[yi+1];
		}
		else
		{
			YYreach[yi] = yi;
			YXreach[yi] = xi;
		}
	}


	// cerr << "#3\n";






	res.pref = X.pref;


	int pi = sz(res.pref);

	if(X.Asum < Ydp[0])
		res.pref.push_back({X.r, X.Asum, 0});

	for(int i = 0; i < sz(Y.pref); i++)
		if(A[Y.pref[i].i + 1] > Y.pref[i].Asum + X.Asum)
			res.pref.push_back({Y.pref[i].i, Y.pref[i].Asum + X.Asum, 0});



	res.suff = Y.suff;

	int si = sz(res.suff);

	if(Y.Asum < Xdp[0])
		res.suff.push_back({Y.l, Y.Asum, 0});

	for(int i = 0; i < sz(X.suff); i++)
		if(A[X.suff[i].i - 1] > X.suff[i].Asum + Y.Asum)
			res.suff.push_back({X.suff[i].i, X.suff[i].Asum + Y.Asum, 0});


	// cerr << "#4\n";

	vpii newpref, newsuff;

	int pi2 = pi;
	int si2 = si;

	for(xi = 0; xi <= Xs; xi++)
	{
		int xiwinners = (xi == Xs ? X.winners : X.suff[xi].winners);

		if(XXreach[xi] == Xs && XYreach[xi] == Ys)
			res.winners += xiwinners;
		else if(XXreach[xi] == Xs)
		{
			// newpref.push_back({XYreach[xi], xiwinners});

			int target = (XYreach[xi] == -1 ? X.r : Y.pref[XYreach[xi]].i);

			// // if(XYreach[xi] == -1)
			while(res.pref[pi2].i < target)
				pi2++;

			res.pref[pi2].winners += xiwinners;
		}
		else if(XYreach[xi] == Ys)
		{

			// newsuff.push_back({XXreach[xi], xiwinners});

			int target = X.suff[XXreach[xi]].i;
			while(res.suff[si2].i > target)
				si2++;

			res.suff[si2].winners += xiwinners;
		}
	}

	pi2 = pi, si2 = si;
	// cerr << "#4-1\n";

	for(yi = 0; yi <= Ys; yi++)
	{
		// cerr << "entered : " << yi << '\n';
		int yiwinners = (yi == Ys ? Y.winners : Y.pref[yi].winners);


		if(YXreach[yi] == Xs && YYreach[yi] == Ys)
			res.winners += yiwinners;
		else if(YXreach[yi] == Xs)
		{
			// newpref.push_back({YYreach[yi], yiwinners});

			int target = (YYreach[yi] == -1 ? X.r : Y.pref[YYreach[yi]].i);

			// // if(XYreach[xi] == -1)
			while(res.pref[pi2].i < target)
				pi2++;

			res.pref[pi2].winners += yiwinners;

		}
		else if(YYreach[yi] == Ys)
		{
			// newsuff.push_back({YXreach[yi], yiwinners});

			int target = (YXreach[yi] == -1 ? Y.l : X.suff[YXreach[yi]].i);

			while(res.suff[si2].i > target)
				si2++;

			res.suff[si2].winners += yiwinners;
		}
	}

	// cerr << "#5\n";

	// for(auto pr : newpref)
	// {
	// 	for(auto& respr : res.pref)
	// 	{
	// 		// assert(pr.first < sz(Y.pref));

	// 		if(pr.first == -1 && respr.i == X.r)
	// 			respr.winners += pr.second;
	// 		else if(pr.first != -1 && respr.i == Y.pref[pr.first].i)
	// 			respr.winners += pr.second;
	// 	}
	// }
	// // cerr << "hello\n";

	// for(auto sf : newsuff)
	// {
	// 	// cerr << sf.first << ' ' << sf.second << '\n';
	// 	for(auto& ressf : res.suff)
	// 	{
	// 		assert(sf.first < sz(X.suff));

	// 		// cerr << "   " << ressf.i << ' ' << ressf.Asum << ' ' << ressf.winners << '\n';

	// 		// cerr << "sff = " <<  sf.first << '\n';
	// 		// cerr << X.suff[sf.first.i] << '\n';

	// 		if(sf.first == -1 && ressf.i == Y.l)
	// 		{
	// 			// cerr << "bye\n";
	// 			ressf.winners += sf.second;
	// 			// cerr << "bye done\n";
	// 		}
	// 		else if(sf.first != -1 && ressf.i == X.suff[sf.first].i)
	// 		{
	// 			// cerr << "bye2\n";
	// 			ressf.winners += sf.second;
	// 		}
	// 	}
	// }


	// Y = info(1);

	// return res;

	// cerr << "combine end\n";
}

info combine(const info& A, const info& B)
{
	info res;
	combine(res, A, B);
	return res;
}


struct segtree
{
	info v;
	segtree* left = NULL;
	segtree* right = NULL;

	segtree()
	{
		;
	}

	segtree(int L, int R)
	{
		if(L == R)
			v = info(L);
		else
		{
			left = new segtree(L, (L+R)/2);
			right = new segtree((L+R)/2+1, R);
			combine(v, left->v, right->v);
		}
	}

	void recompute(int I)
	{
		// cerr << "recompute : " << v.l << ' ' << v.r << ' ' << I << '\n';
		if(v.l == v.r)
			v = info(v.l);
		else
		{
			if(I <= (v.l+v.r)/2)
				left->recompute(I);
			else
				right->recompute(I);

			// cerr << "###\n";

			combine(v, left->v, right->v);

			// cerr << "combine done\n";
		}
		// cerr << "done\n";
	}

	info range(int L, int R)
	{
		if(L <= v.l && v.r <= R)
			return v;
		else if(R <= (v.l+v.r)/2)
			return left->range(L, R);
		else if(L >= (v.l+v.r)/2+1)
			return right->range(L, R);
		else
			return combine(left->range(L, R), right->range(L, R));
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	A = vll(1+N);
	for(int i = 1; i <= N; i++)
		cin >> A[i];

	// cerr << "done\n";

	segtree S(1, N);

	// cerr << "done2\n";


	cin >> Q;
	for(int j = 1; j <= Q; j++)
	{
		int T;
		cin >> T;

		if(T == 1)
		{
			int X, Y;
			cin >> X >> Y;
			A[X] = Y;
			S.recompute(X);
			// cerr << "hello\n";
		}
		else
		{
			int L, R;
			cin >> L >> R;
			cout << S.range(L, R).winners << '\n';
		}
	}
}		

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 12 / 12
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 17 / 17