oj.uz

Submission #683257

# Submission time Handle Problem Language Result Execution time Memory
683257 2023-01-18T04:26:13 Z badont Growing Trees (BOI11_grow) C++17
100 / 100
 112 ms 3636 KB 
#include<bits/stdc++.h>
using namespace std;

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
LL T;

template<typename T>
struct fen {
	vector<T> tr;
	LL mxn;

	fen(LL sz) {
		mxn = sz;
		tr.assign(sz + 5, 0);
	}

	void upd(LL g, T k) {
		g++;
		assert(g != 0);
		for (; g <= mxn; g += g&-g)
			tr[g] += k;
	}

	T ge(LL g) {
		g++;
		T res = 0;
		for (; g; g -= g&-g)
			res += tr[g];
		return res;
	}

	T rng(LL l, LL r) { return ge(r) - ge(l - 1); }

	//maxi and mini only work with positive numbers
	LL maxi(T k) {
		//max i such that ge(i) <= k.
		//log(n) vs log^2(n) binary search
		T running = 0; LL res = 0;
		LL lg = 32 - __builtin_clz(mxn);

		for (int i = lg; i>=0; i--) {
			if (res + (1LL << i) > mxn) continue;
			if (running + tr[res + (1LL << i)] > k) continue;
			running += tr[res + (1LL << i)];
			res += (1LL << i);
		}

		return res;
	}

	LL mini(T k) {
		//kth order statistic
		T running = 0; LL res = 0;
		LL lg = 32 - __builtin_clz(mxn);

		for (int i = lg; i>=0; i--) {
			if (res + (1LL << i) > mxn) continue;
			if (running + tr[res + (1LL << i)] >= k) continue;
			running += tr[res + (1LL << i)];
			res += (1LL << i);
		}

		return res + 1;
	}
};

void solve() {
	LL n, m;
	cin >> n >> m;

	vector<LL> a(n);
	for (auto& u : a)
		cin >> u;

	sort(all(a));
	fen<LL> delt(n);

	auto get = [&](LL in) -> LL {
		return a[in] + delt.ge(in);
	};

	auto up_range = [&](LL l, LL r, LL k) -> void {
		if (l > r) return;
		delt.upd(l, 1);
		delt.upd(r + 1, -1);
	};

	auto find_low = [&](LL in) -> LL {
		//finds lowest index point with value equal to index
		LL target = get(in);
		LL lo = 0, hi = in, mid;
		while (lo < hi) {
			mid = (lo + hi) >> 1;
			if (get(mid) == target)
				hi = mid;
			else lo = mid + 1;
		}
		return lo;
	};

	auto find_high = [&](LL in) -> LL {
		LL target = get(in);
		LL lo = in, hi = n - 1, mid;
		while (lo < hi) {
			mid = (lo + hi + 1) >> 1;
			if (get(mid) == target) 
				lo = mid;
			else hi = mid - 1;
		}
		return lo;
	};

	auto find_point = [&](LL k) -> LL {
		//finds minimal index with value >= k
		LL lo = 0, hi = n, mid;
		while (lo < hi) {
			mid = (lo + hi) >> 1;
			if (get(mid) >= k) hi = mid;
			else lo = mid + 1;
		}
		return lo;
	};

	while (m--) {
		char T; cin >> T;
		if (T == 'F') {
			LL c, q;
			cin >> q >> c;

			LL l = find_point(c);
			//debug(l);
			if (l != n) {
				LL r = min(n - 1, l + q - 1);

				//debug(r);

				LL low = find_low(r);
				LL high = find_high(r);

				//debug(low, high);

				up_range(l, low - 1, 1);
				LL used = max(low - l, 0LL);
				//debug(used);
				LL rem = q - used;

				//debug(rem);

				//update last rem
				rem = min(rem, high - low + 1);
				up_range(high - rem + 1, high, 1);
			}
		} else {
			LL lo, hi; cin >> lo >> hi;
			LL r = find_point(hi + 1); r--;
			LL l = find_point(lo);

			cout << r - l + 1 << "\n";
		}

		F0R (i, n) debug(get(i));
		debug('\n');
	}
}

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

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

Compilation message

grow.cpp: In function 'void solve()':
grow.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) "zzz"
      |                    ^~~~~
grow.cpp:195:14: note: in expansion of macro 'debug'
  195 |   F0R (i, n) debug(get(i));
      |              ^~~~~
grow.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) "zzz"
      |                    ^~~~~
grow.cpp:196:3: note: in expansion of macro 'debug'
  196 |   debug('\n');
      |   ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1912 KB Output is correct
2 Correct 98 ms 3308 KB Output is correct
3 Correct 59 ms 3248 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 392 KB Output is correct
4 Correct 2 ms 328 KB Output is correct
5 Correct 50 ms 1452 KB Output is correct
6 Correct 54 ms 1644 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 30 ms 1152 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 784 KB Output is correct
2 Correct 60 ms 1820 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 39 ms 1312 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 764 KB Output is correct
2 Correct 57 ms 1748 KB Output is correct
3 Correct 6 ms 464 KB Output is correct
4 Correct 50 ms 1740 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 1408 KB Output is correct
2 Correct 86 ms 2812 KB Output is correct
3 Correct 15 ms 1000 KB Output is correct
4 Correct 51 ms 2828 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 1492 KB Output is correct
2 Correct 95 ms 2964 KB Output is correct
3 Correct 57 ms 3052 KB Output is correct
4 Correct 15 ms 1004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 1712 KB Output is correct
2 Correct 67 ms 3016 KB Output is correct
3 Correct 73 ms 3344 KB Output is correct
4 Correct 14 ms 972 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 1744 KB Output is correct
2 Correct 97 ms 2856 KB Output is correct
3 Correct 24 ms 2516 KB Output is correct
4 Correct 57 ms 2896 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1868 KB Output is correct
2 Correct 95 ms 3364 KB Output is correct
3 Correct 112 ms 3636 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 2388 KB Output is correct