Submission #386914

#	Time	Username	Problem	Language	Result	Execution time	Memory
386914		peijar	Growing Trees (BOI11_grow)	C++17	100 / 100	140 ms	4204 KiB

grow

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

struct Fenwick
{
	int N;
	vector<int> bit;

	Fenwick(int n) : N(n+1), bit(N) {}

	void updatePos(int pos, int add)
	{
		for (pos++; pos < N; pos += pos & -pos)
			bit[pos] += add;
	}

	int queryRange(int r) // < r
	{
		int ret(0);
		for (; r; r -= r & -r)
			ret += bit[r];
		return ret;
	}

	int queryRange(int l, int r) // [l,r)
	{
		return queryRange(r) - queryRange(l);
	}

	void updateRange(int l, int r, int add) // [l, r)
	{
		updatePos(l, add);
		updatePos(r, -add);
	}

	int queryPoint(int pos)
	{
		return queryRange(pos+1);
	}

	int nbAvant(int val) // nb elements < val
	{
		if (queryPoint(0) >= val)
			return 0;
		int deb(1), fin(N-1);
		while (deb < fin)
		{
			int mil = (deb + fin+1) / 2;
			if (queryPoint(mil-1) >= val)
				fin = mil-1;
			else
				deb = mil;
		}
		return deb;
	}

	int nbDansSeg(int L, int R) // [L, R)
	{
		return nbAvant(R) - nbAvant(L);
	}
};

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbArbres, nbRequetes;
	cin >> nbArbres >> nbRequetes;
	Fenwick fen(nbArbres);
	vector<int> hauteurs(nbArbres);
	for (auto &v : hauteurs)
		cin >> v;
	sort(hauteurs.begin(), hauteurs.end());

	for (int iArbre(0); iArbre < nbArbres; ++iArbre)
		fen.updateRange(iArbre, iArbre+1, hauteurs[iArbre]);

	for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) 
	{
		char typeRequete;
		cin >> typeRequete;
		if (typeRequete == 'C')
		{
			int L, R;
			cin >> L >> R;
			cout << fen.nbDansSeg(L, R+1) << '\n';
		}
		else
		{
			int nbUpdates, valUpdate;
			cin >> nbUpdates >> valUpdate;
			int nbPasBon = fen.nbAvant(valUpdate);
			if (nbArbres - nbPasBon <= nbUpdates)
				fen.updateRange(nbPasBon, nbArbres, 1);
			else
			{
				int lastValUpd = fen.queryPoint(nbPasBon + nbUpdates-1);
				int premierLastVal = fen.nbAvant(lastValUpd);
				int dernierLastVal = fen.nbAvant(lastValUpd+1)-1;

				fen.updateRange(nbPasBon, premierLastVal, 1);
				fen.updateRange(dernierLastVal +1-(nbUpdates - (premierLastVal - nbPasBon)), dernierLastVal+1, 1);
			}
		}
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10