oj.uz

Submission #954554

# Submission time Handle Problem Language Result Execution time Memory
954554 2024-03-28T06:49:27 Z Amaarsaa Growing Trees (BOI11_grow) C++14
0 / 100
 404 ms 13304 KB 
#include<bits/stdc++.h>

using namespace std;
#define lc (p<<1)
#define rc (p<<1) + 1
using ll = long long ;
const ll N = 1e5 + 4;
pair < ll, ll > P[N];
ll a[N], n;

struct node {
	ll lzadd;
	ll min;
};
node tree[8 * N];

void pushdown(ll p, ll lo, ll hi) {
	if ( tree[p].lzadd != 0) {
		tree[lc].lzadd += tree[p].lzadd;
		tree[lc].min += tree[p].lzadd;
		tree[rc].lzadd += tree[p].lzadd;
		tree[rc].min += tree[p].lzadd;
		tree[p].lzadd = 0;
	}
	return ;
}

void pushup(ll p, ll lo, ll hi) {
	tree[p].min = min(tree[lc].min, tree[rc].min);
}

void Build (ll p, ll lo, ll hi) {
	ll mid = (lo + hi)/2;
	tree[p].lzadd = 0;
	if ( lo == hi) {
		tree[p].min = a[lo];
		return ;
	}
	Build(lc, lo, mid);
	Build(rc, mid + 1, hi);
	pushup(p, lo, hi);
	return ;
}
ll find(ll p, ll lo, ll hi, ll x) {
	ll mid = (lo + hi)/2;
	pushdown(p, lo, hi);
	if ( lo == hi) return tree[p].min;
	if ( x <= mid) return find(lc, lo, mid, x);
	return find(rc, mid + 1, hi, x);
}
void update(ll p, ll lo, ll hi, ll l, ll r, ll x) {
	ll mid = (lo + hi)/2;
	pushdown(p, lo, hi);
	if ( lo > r || l > hi) return ;
	if ( l <= lo && hi <= r) {
		tree[p].lzadd = x;
		tree[p].min += x;
		return ;
	}
	update(lc, lo, mid, l, r, x);
	update(rc, mid + 1, hi, l, r, x);
	pushup(p, lo, hi);
}
ll lowerb(ll x) {
	if ( x > find(1, 1, n, n)) return n +1;
	ll lo, hi, mid;
	lo = 1;
	hi = n + 1;
	while ( lo < hi) {
		mid = (lo + hi)/2;
		if (find(1, 1, n, mid) < x) lo = mid + 1;
		else hi =mid;
	}
	return lo;
}
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll q, i, x, l, y, s;
	
	cin >> n >> q;
	
	for (i = 1; i <= n; i ++) cin >> a[i];
	
	sort ( a + 1, a + n + 1);
	
	
	Build(1, 1, n);
	
	char ch;
	while ( q-- ) {
		cin >> ch;
		if ( ch == 'F') {
			cin >> x >> y;
			swap(x, y);
			l = lowerb(x);
			if ( l + y - 1 >= n) {
				update(1, 1, n, l, n, 1);
			}
			else {
				s = lowerb(find(1, 1, n, l + y - 1));
				update(1, 1, n, l,s - 1, 1);
		//		cout << x << " " << l << " " << s << endl;
				y -= (s - l);
		//		cout << y << ">" << endl;
				s = lowerb(find(1, 1, n, l + y - 1) + 1);
				s --;
			//	cout << s << endl;
				update(1, 1, n, s - y + 1, s, 1);
			}
		}
		else {
			cin >> x >> y;
			cout << lowerb(y + 1) - lowerb(x) << endl;
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 11952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 227 ms 5716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 5832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 7832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 249 ms 11896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 11836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 404 ms 12840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 261 ms 12148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 397 ms 13304 KB Output isn't correct
2 Halted 0 ms 0 KB -