oj.uz

Submission #394841

# Submission time Handle Problem Language Result Execution time Memory
394841 2021-04-27T10:53:14 Z SavicS Growing Trees (BOI11_grow) C++14
100 / 100
 115 ms 2028 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, q;
int niz[maxn];

ll dud[maxn];
void upd(int x, ll val) {
	while(x <= n) {
		dud[x] += val;
		x += x&(-x);
	}
}

ll query(int x) {
	ll sum = 0;
	while(x > 0) {
		sum += dud[x];
		x -= x&(-x);
	}
	return sum;
}

void add_range(int L, int R, int X) {
	upd(L, X);
	upd(R + 1, -X);
}

int main() 
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	cin >> n >> q;
	ff(i,1,n)cin >> niz[i];
	sort(niz + 1, niz + n + 1);

	ff(i,1,n)add_range(i, i, niz[i]);


	while(q--) {
		char tip;
		cin >> tip;

		if(tip == 'F') {
			int C, H;
			cin >> C >> H;

			int od = 0;
			{
				int l = 1, r = n, ans = n + 1;
				while(l <= r) {
					int mid = (l + r) / 2;
					if(query(mid) >= H) {
						ans = mid;
						r = mid - 1;
					} else l = mid + 1;
				}

				// od kog indeska su >= H
				od = ans;

			}

			if(od == n + 1)continue;

			int L = od, R = min(n, od + C - 1);
			if(R == n || query(R + 1) != query(R)) {
				add_range(L, R, 1);
				continue;
			}

			int first = 0;
			{
				int l = L, r = R, ans = 0;
				while(l <= r) {
					int mid = (l + r) / 2;
					if(query(mid) == query(R + 1)) {
						ans = mid;
						r = mid - 1;
					} else l = mid + 1;
				}

				first = ans;

			}
			int last = 0;
			{
				int l = first, r = n, ans = 0;
				while(l <= r) {
					int mid = (l + r) / 2;
					if(query(mid) == query(first)) {
						ans = mid;
						l = mid + 1;
					} else r = mid - 1;
				}

				last = ans;

			}

			add_range(L, first - 1, 1);
			int ost = R - first + 1;
			add_range(max(first, last - ost + 1), last, 1);

		}

		if(tip == 'C') {
			int A, B;
			cin >> A >> B;

			int L = 0;
			{
				int l = 1, r = n, ans = n + 1;
				while(l <= r) {
					int mid = (l + r) / 2;
					if(query(mid) >= A) {
						ans = mid;
						r = mid - 1;
					} else l = mid + 1;
				}

				L = ans;
			}

			int R = 0;
			{
				int l = 1, r = n, ans = 0;
				while(l <= r) {
					int mid = (l + r) / 2;
					if(query(mid) <= B) {
						ans = mid;
						l = mid + 1;
					} else r = mid - 1;
				}

				R = ans;

			}

			cout << R - L + 1 << '\n';

		}

	}

	return 0;
}
/**

5 7
1 3 2 5 2
F 2 1
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5

// probati bojenje sahovski ili slicno

**/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1476 KB Output is correct
2 Correct 104 ms 1448 KB Output is correct
3 Correct 43 ms 1160 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 52 ms 564 KB Output is correct
6 Correct 64 ms 724 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 30 ms 520 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 752 KB Output is correct
2 Correct 62 ms 708 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 39 ms 588 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 756 KB Output is correct
2 Correct 71 ms 860 KB Output is correct
3 Correct 6 ms 332 KB Output is correct
4 Correct 63 ms 716 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1184 KB Output is correct
2 Correct 109 ms 1368 KB Output is correct
3 Correct 19 ms 588 KB Output is correct
4 Correct 40 ms 1144 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 1264 KB Output is correct
2 Correct 114 ms 1308 KB Output is correct
3 Correct 43 ms 1100 KB Output is correct
4 Correct 19 ms 540 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1452 KB Output is correct
2 Correct 84 ms 1476 KB Output is correct
3 Correct 48 ms 1152 KB Output is correct
4 Correct 18 ms 620 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1468 KB Output is correct
2 Correct 115 ms 1348 KB Output is correct
3 Correct 32 ms 1612 KB Output is correct
4 Correct 68 ms 1356 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 1480 KB Output is correct
2 Correct 101 ms 1412 KB Output is correct
3 Correct 98 ms 1356 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 2028 KB Output is correct