oj.uz

답안 #394835

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
394835 2021-04-27T10:45:49 Z SavicS Growing Trees (BOI11_grow) C++14
100 / 100
 271 ms 3684 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 <= maxn) {
		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 << endl;

		}

	}

	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

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 2628 KB Output is correct
2 Correct 166 ms 2996 KB Output is correct
3 Correct 46 ms 2944 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 8 ms 336 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 6 ms 336 KB Output is correct
5 Correct 159 ms 1456 KB Output is correct
6 Correct 212 ms 1576 KB Output is correct
7 Correct 7 ms 460 KB Output is correct
8 Correct 154 ms 1292 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 1604 KB Output is correct
2 Correct 192 ms 1720 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 171 ms 1248 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 1856 KB Output is correct
2 Correct 219 ms 1732 KB Output is correct
3 Correct 7 ms 460 KB Output is correct
4 Correct 196 ms 1828 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 2124 KB Output is correct
2 Correct 179 ms 2500 KB Output is correct
3 Correct 48 ms 908 KB Output is correct
4 Correct 42 ms 2500 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 2276 KB Output is correct
2 Correct 181 ms 2668 KB Output is correct
3 Correct 48 ms 2756 KB Output is correct
4 Correct 49 ms 896 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 2372 KB Output is correct
2 Correct 153 ms 2628 KB Output is correct
3 Correct 50 ms 2912 KB Output is correct
4 Correct 48 ms 924 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 168 ms 3012 KB Output is correct
2 Correct 182 ms 2500 KB Output is correct
3 Correct 35 ms 2204 KB Output is correct
4 Correct 144 ms 2528 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 2888 KB Output is correct
2 Correct 180 ms 3020 KB Output is correct
3 Correct 108 ms 3248 KB Output is correct

Subtask #10
10.0 / 10.0

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