oj.uz

Submission #520502

# Submission time Handle Problem Language Result Execution time Memory
520502 2022-01-30T07:46:41 Z blue Growing Trees (BOI11_grow) C++17
100 / 100
 165 ms 9828 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

const int mx = 100'000;

const int Z = (1<<17);


vll delta(1+mx);

int N, M;


struct segtree
{
	vi l = vi(Z<<1);
	vi r = vi(Z<<1);
	vll sm = vll(Z<<1);
	vll mxs = vll(Z<<1);

	segtree()
	{
		;
	}

	void build(int i, int L, int R)
	{
		// cerr << "build " << i << ' ' << L << ' ' << R << '\n';
		l[i] = L;
		r[i] = R;
		if(l[i] == r[i])
		{
			// cerr << "case : \n";
			sm[i] = delta[l[i]];
			mxs[i] = sm[i];
		}
		else
		{
			build(2*i, L, (L+R)/2);
			build(2*i+1, (L+R)/2+1, R);
			sm[i] = sm[2*i] + sm[2*i+1];
			mxs[i] = max(mxs[2*i], sm[2*i] + mxs[2*i+1]);
		}
		// cerr << "quit " << i << ' ' << L << ' ' << R << '\n';
	}

	int first_geq(int i, ll s)
	{
		// cerr << i << ' ' << l[i] << ' ' << r[i] << " : " << sm[i] << ' ' << s << '\n';
		if(mxs[i] < s) return N+1;
		else if(l[i] == r[i]) return l[i];
		else if(mxs[i<<1] >= s) return first_geq(i<<1, s);
		else return first_geq((i<<1) + 1, s - sm[i<<1]);
	}

	int first_geq(ll s) {return first_geq(1, s);}

	void add(int i, int I, ll V)
	{
		if(l[i] != r[i])
		{
			if(I <= (l[i] + r[i])/2) add(2*i, I, V);
			else add(2*i+1, I, V);

			sm[i] = sm[2*i] + sm[2*i+1];
			mxs[i] = max(mxs[2*i], sm[2*i] + mxs[2*i+1]);
		}
		else
		{
			sm[i] += V;
			mxs[i] += V;
		}
	}

	void add(int I, int V) {if(1 <= I && I <= N) add(1, I, V);}

	int get_sum(int i, int I)
	{
		if(l[i] == r[i]) return sm[i];
		else if(I <= (l[i] + r[i])/2) return get_sum(i<<1, I);
		else return sm[(i<<1)] + get_sum((i<<1) + 1, I);
	}

	// void dfs(int i)
	// {
	// 	// cerr << l[i] << ' ' << r[i] << " : " << sm[i] << '\n';
	// 	if(l[i] != r[i]) dfs(2*i), dfs(2*i+1);
	// }
};

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

	cin >> N >> M;

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

	sort(init_h.begin(), init_h.end());

	for(int i = 1; i <= N; i++) delta[i] = init_h[i] - init_h[i-1];


	segtree S;
	S.build(1, 1, N+1);

	// cerr << "\n\n\n";
	// S.dfs(1);



	for(int q = 1; q <= M; q++)
	{
		// if(q % 1 == 0)
		// 	cerr << "query = " << q << '\n';
		char t;
		cin >> t;

		if(t == 'F')
		{
			ll c, h;
			cin >> c >> h;

			int stp = S.first_geq(h);

			// cerr << "stp = " << stp << '\n';

			if(stp >= N+1) continue;

			int ep = min(stp + c - 1, (ll)N);

			// cerr << "ep = " << ep << '\n';


			ll ep_val = S.get_sum(1, ep);

			// cerr << "ep_val = " << ep_val << '\n';

			int last_start = S.first_geq(1, ep_val);
			int last_end = S.first_geq(1, ep_val+1) - 1;

			// cerr << "ls, le = " << last_start << ' ' << last_end << '\n';


			int last_count = ep - last_start + 1;

			// cerr << "lc = " << last_count << '\n';

			S.add(last_end - last_count + 1, +1);


			// cerr << "done\n";




			S.add(last_end+1, -1);






			// cerr << last_end - last_count + 1 << " [) " << last_end+1 << '\n';

			S.add(stp, +1);
			S.add(last_start, -1);

			// cerr << stp << " : " << last_start << '\n';



			// cerr << S.first_geq(2) << '\n';
		}
		else
		{
			ll mn, mx;
			cin >> mn >> mx;

			cout << S.first_geq(1, mx+1) - S.first_geq(1, mn) << '\n';
		}
	}

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8160 KB Output is correct
2 Correct 120 ms 9624 KB Output is correct
3 Correct 124 ms 9560 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 5 ms 7244 KB Output is correct
3 Correct 5 ms 7244 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Correct 45 ms 7520 KB Output is correct
6 Correct 43 ms 7632 KB Output is correct
7 Correct 8 ms 7244 KB Output is correct
8 Correct 24 ms 7536 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 7620 KB Output is correct
2 Correct 45 ms 7684 KB Output is correct
3 Correct 4 ms 7328 KB Output is correct
4 Correct 26 ms 7500 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 7748 KB Output is correct
2 Correct 44 ms 7596 KB Output is correct
3 Correct 10 ms 7244 KB Output is correct
4 Correct 44 ms 7620 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 7876 KB Output is correct
2 Correct 99 ms 8000 KB Output is correct
3 Correct 16 ms 7780 KB Output is correct
4 Correct 87 ms 9160 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7924 KB Output is correct
2 Correct 107 ms 9244 KB Output is correct
3 Correct 127 ms 9468 KB Output is correct
4 Correct 15 ms 7740 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 8096 KB Output is correct
2 Correct 73 ms 9272 KB Output is correct
3 Correct 110 ms 9544 KB Output is correct
4 Correct 15 ms 7756 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 7996 KB Output is correct
2 Correct 99 ms 9232 KB Output is correct
3 Correct 37 ms 8724 KB Output is correct
4 Correct 93 ms 9264 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 8140 KB Output is correct
2 Correct 104 ms 9564 KB Output is correct
3 Correct 165 ms 9828 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 8552 KB Output is correct