oj.uz

답안 #386914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386914 2021-04-07T16:00:41 Z peijar Growing Trees (BOI11_grow) C++17
100 / 100
 140 ms 4204 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 3052 KB Output is correct
2 Correct 119 ms 3564 KB Output is correct
3 Correct 43 ms 3308 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 3 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 55 ms 1516 KB Output is correct
6 Correct 63 ms 1772 KB Output is correct
7 Correct 5 ms 492 KB Output is correct
8 Correct 24 ms 1260 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 1772 KB Output is correct
2 Correct 64 ms 1900 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 34 ms 1388 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 1940 KB Output is correct
2 Correct 69 ms 1772 KB Output is correct
3 Correct 7 ms 492 KB Output is correct
4 Correct 63 ms 1900 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 2540 KB Output is correct
2 Correct 107 ms 2924 KB Output is correct
3 Correct 20 ms 1004 KB Output is correct
4 Correct 34 ms 2924 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 2668 KB Output is correct
2 Correct 108 ms 3180 KB Output is correct
3 Correct 38 ms 3052 KB Output is correct
4 Correct 25 ms 1004 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 2796 KB Output is correct
2 Correct 71 ms 3052 KB Output is correct
3 Correct 42 ms 3436 KB Output is correct
4 Correct 19 ms 1004 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 3436 KB Output is correct
2 Correct 118 ms 2924 KB Output is correct
3 Correct 32 ms 2668 KB Output is correct
4 Correct 52 ms 2924 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 3180 KB Output is correct
2 Correct 140 ms 3564 KB Output is correct
3 Correct 120 ms 3820 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 4204 KB Output is correct