oj.uz

Submission #531041

# Submission time Handle Problem Language Result Execution time Memory
531041 2022-02-27T13:15:07 Z xuliu Growing Trees (BOI11_grow) C++17
100 / 100
 116 ms 3736 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

const int mod = 1e9 + 7;
const ll infL = 1e18 + 7;
const int inf = 1e9 + 7;

//void add(int &a, int b) { a = (a+b)%mod; }
//int add(int a, int b, int c) { int res = (((a+b)%mod) + c)%mod; return res; }

struct BIT {
	int n; vector<ll> bit;
	BIT(int size) {
		n = size;
		bit.assign(n, 0);
	}
	ll sum(int r) {
		ll ret = 0;
		for(; r >= 0; r = (r & (r+1))-1)
			ret += bit[r];
		return ret;
	}
	void add(int idx, ll d) {
		for(; idx < n; idx = idx|(idx+1))
			bit[idx] += d;
	}
};

void add(BIT &b, int l, int r, ll v) {
	b.add(l, v);
	b.add(r+1, -v);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin>>n>>q;
	vector<ll> tr(n);
	for(int i=0; i<n; i++) {
		cin>>tr[i];
	}
	sort(tr.begin(), tr.end());
	BIT bit(n+5);
	for(int i=0; i<n; i++) add(bit, i+1, i+1, tr[i]);
	for(int i=n+1; i<(n+5); i++) add(bit, i, i, 2*inf);
	while(q--) {
		char ch; cin>>ch;
		if(ch == 'C') {
			int l, r; cin>>l>>r;
			int lo = 1, hi = n;
			while(lo < hi) {
				int m = (lo+hi)/2;
				if(bit.sum(m) >= l)
					hi = m;
				else
					lo = m+1;
			}
			int pozp = lo; lo = 1; hi = n;
			while(lo < hi) {
				int m = (lo+hi+1)/2;
				if(bit.sum(m) > r)
					hi = m - 1;
				else
					lo = m;
			}
			int pozk = lo;
			debug cerr<<"pozp: "<<pozp<<" ; pozk = "<<pozk<<"\n";
			if(bit.sum(pozp) < l || bit.sum(pozp) > r) {
				cout<<0<<"\n";
				continue;
			}
			int ret = pozk - pozp + 1;
			cout<<ret<<"\n";
		}
		else {
			int c, h; cin>>c>>h;
			int lo = 1, hi = n;
			while(lo < hi) {
				int m = (lo+hi)/2;
				if(bit.sum(m) >= h)
					hi = m;
				else
					lo = m+1;
			}
			int pp = lo; // position of first tree with height >= h
			debug cerr<<"pp: "<<pp<<"\n";
			if(bit.sum(pp) < h) {
				debug cerr<<"0 elements with >= h\n";
				continue;
			}
			if(n-pp+1 <= c) {
				debug cerr<<"all from ["<<pp<<", "<<n<<"] increased\n";
				// all tree can be increased
				add(bit, pp, n, 1);
				continue;
			}
			int valk = bit.sum(pp+c-1); // value of last 'increased' element
			debug cerr<<"valk = "<<valk<<"\n";
			int toadd = c;
			if(valk > bit.sum(pp)) {
				lo = 1; hi = n;
				while(lo < hi) {
					int m = (lo+hi+1)/2;
					if(bit.sum(m) > valk-1)
						hi = m - 1;
					else
						lo = m;
				}
				int pbl = lo; // postion of last before valk
				debug cerr<<"adding on ["<<pp<<", "<<pbl<<"] - 1\n";
				add(bit, pp, pbl, 1);
				toadd = c - (pbl-pp+1);
			}
			lo = 1; hi = n;
			while(lo < hi) {
				debug cerr<<"{lo, hi} = {"<<lo<<", "<<hi<<"}\n";
				int m = (lo+hi+1)/2;
				if(bit.sum(m) > valk)
					hi = m - 1;
				else
					lo = m;
			}
			int pck = lo; // postiono of last great element
			debug cerr<<"adding on ["<<pck-toadd+1<<", "<<pck<<"] - 2 # lo = "<<lo<<"\n";
			add(bit, pck-toadd+1, pck, 1);
			debug {
				cerr<<"AFTER: ";
				for(int i=1; i<=n; i++) cerr<<bit.sum(i)<<" ";
				cerr<<"\n\n";
			}
		}
	}
	debug {
		cerr<<"AFTER: ";
		for(int i=1; i<=n; i++) cerr<<bit.sum(i)<<" ";
		cerr<<"\n\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2020 KB Output is correct
2 Correct 109 ms 3332 KB Output is correct
3 Correct 38 ms 3300 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 3 ms 332 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 49 ms 516 KB Output is correct
6 Correct 57 ms 776 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 25 ms 568 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 748 KB Output is correct
2 Correct 75 ms 708 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 39 ms 684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 808 KB Output is correct
2 Correct 63 ms 1732 KB Output is correct
3 Correct 6 ms 452 KB Output is correct
4 Correct 57 ms 1720 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 1484 KB Output is correct
2 Correct 93 ms 2988 KB Output is correct
3 Correct 18 ms 968 KB Output is correct
4 Correct 30 ms 2700 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1664 KB Output is correct
2 Correct 115 ms 2912 KB Output is correct
3 Correct 36 ms 3052 KB Output is correct
4 Correct 17 ms 972 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 1748 KB Output is correct
2 Correct 64 ms 2980 KB Output is correct
3 Correct 40 ms 3212 KB Output is correct
4 Correct 17 ms 972 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 2020 KB Output is correct
2 Correct 96 ms 1768 KB Output is correct
3 Correct 27 ms 2492 KB Output is correct
4 Correct 53 ms 2880 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 2012 KB Output is correct
2 Correct 110 ms 3280 KB Output is correct
3 Correct 111 ms 3736 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 2244 KB Output is correct