Submission #531037

#	Time	Username	Problem	Language	Result	Execution time	Memory
531037		xuliu	Growing Trees (BOI11_grow)	C++17	10 / 100	112 ms	4140 KiB

grow

#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 c; cin>>c;
		if(c == '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) {
				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(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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10