oj.uz

Submission #954556

# Submission time Handle Problem Language Result Execution time Memory
954556 2024-03-28T06:57:56 Z Amaarsaa Growing Trees (BOI11_grow) C++14
0 / 100
 343 ms 11308 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 + 2];

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;
	while ( lo < hi) {
		mid = (lo + hi)/2;
		if (find(1, 1, n, mid) < x) lo = mid + 1;
		else hi =mid;
	}
	return lo;
}
ll upperb(ll x) {
	if ( x > find(1, 1, n, n)) return n +1;
	ll lo, hi, mid;
	lo = 1;
	hi = n;
	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, j, 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 = upperb(find(1, 1, n, l + y - 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;
		}
	//	for (j= 1; j <= n; j ++) cout << find(1, 1, n, j) << " ";
	//	cout << endl;
	}
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:93:20: warning: unused variable 'j' [-Wunused-variable]
   93 |  ll q, i, x, l, y, j, s;
      |                    ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 175 ms 4772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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