Submission #1122209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122209		vjudge1	Growing Trees (BOI11_grow)	C++14	100 / 100	122 ms	10332 KiB

grow

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

const ll mod = 1e9 + 7;
const int N = 1e5 + 5;

int n, q;
int val[100005];

struct node{
	int Max, cntMax;
	int Min, cntMin;
	int lzSum;
	node(){
		Max = cntMax = 0;
		Min = cntMin = 0;
		lzSum = 0;
	}
	
	void apd(int Sum, int l, int r){
		if (Sum){
			Max += Sum;
			Min += Sum;
			lzSum += Sum;
		}
		
	}
	
	node operator + (const node  &other) const{
		node res;
		res.Max = max(Max, other.Max);
		res.Min = min(Min, other.Min);
		
		if (res.Max == Max) res.cntMax += cntMax;
		if (res.Max == other.Max) res.cntMax += other.cntMax;
		
		if (res.Min == Min) res.cntMin += cntMin;
		if (res.Min == other.Min) res.cntMin += other.cntMin;
		
		return res;
	}
};
struct s3x{
	node st[400005];
	
	void build(int l, int r, int id){
		if (l == r){
			st[id].cntMax = st[id].cntMin = 1;
			st[id].apd(val[l], l, r);
			return;
		}
		
		int mid = (l + r) >> 1;
		build(l, mid, (id << 1));
		build(mid + 1, r, (id << 1) + 1);
		
		st[id] = st[(id << 1)] + st[(id << 1) + 1];
	}
	
	void down(int l, int r, int id){
		int mid = (l + r) >> 1;
		st[(id << 1)].apd(st[id].lzSum, l, mid);
		st[(id << 1) + 1].apd(st[id].lzSum, mid + 1, r);
		st[id].lzSum = 0;
	}
	
	void upd(int l, int r, int id, int u, int v, int B){
		if (r < u || v < l) return;
		if (u <= l && r <= v){
			
			st[id].apd(B, l, r);
			//cerr << "boom updted " << l <<" " <<r  << " -> " << st[id].Min << " " << st[id].cntMin <<endl;
			return;
		}
		down(l, r, id);
		int mid = (l + r) >> 1;
		upd(l, mid, (id << 1), u, v, B);
		upd(mid + 1, r, (id << 1) + 1, u, v, B);
		
	
		st[id] = st[(id << 1)] + st[(id << 1) + 1];	
		//cerr << l <<" " << r << "-" << st[id].Min <<" " << st[id].cntMin  <<" " << st[(id << 1) + 1].Min <<" " << st[(id << 1)].Min<<endl;
	}
	
	int getPos(int val){
		int id = 1;
		int l = 1, r = n;
		
		if (st[id].Max < val) return n + 1;
		while (l < r){
			down(l, r, id);
			//cerr << l <<" " << r << " " << st[id << 1].Max  <<" " << val <<endl;
			if (st[(id << 1)].Max >= val) {
				r = (l + r) >> 1;
				id = (id << 1);
			} 
			else{
				l = ((l + r) >> 1) + 1;
				id = (id << 1) + 1;
			}
		}
		return l;
	}
	
	pair <int, int> getMax(int l, int r, int id, int u, int v){
		if (r < u || v < l) return {0, 0};
		if (u <= l && r <= v) return {st[id].Max, st[id].cntMax};
		
		down(l, r, id);
		int mid = (l + r) >> 1;
		
		pair <int, int> get1 = getMax(l, mid, (id << 1), u, v);
		pair <int, int> get2 = getMax(mid + 1, r, (id << 1) + 1, u, v);
		pair <int, int> get3;
		get3.first = max(get1.first, get2.first);
		get3.second = get1.second * (get1.first == get3.first) + get2.second * (get2.first == get3.first);
		
		return get3;
	}
	
	pair <int, int> getMin(int l, int r, int id, int u, int v){
		if (r < u || v < l) return {1e9, 0};
		if (u <= l && r <= v) return {st[id].Min, st[id].cntMin};
		
		down(l, r, id);
		int mid = (l + r) >> 1;
		
		pair <int, int> get1 = getMin(l, mid, (id << 1), u, v);
		pair <int, int> get2 = getMin(mid + 1, r, (id << 1) + 1, u, v);
		pair <int, int> get3;
		get3.first = min(get1.first, get2.first);
		get3.second = get1.second * (get1.first == get3.first) + get2.second * (get2.first == get3.first);
		return get3;
	}
	void transfer(int l, int mid, int r){
		upd(1, n, 1, l, min(mid, l + r - mid - 1), -1);
		upd(1, n, 1, max(mid + 1, r - (mid - l + 1) + 1), r, 1);
	}
} IT;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

//	freopen("test.inp", "r", stdin);
//	freopen("test.out", "w", stdout);
	cin >> n >> q;

	for (int i = 1; i <= n; i ++ ){
		cin >> val[i];
	}
	sort(val + 1, val + n + 1);
	IT.build(1, n, 1);

	while (q -- ){
		char type;
		int a, b;
		cin >> type >> a >> b;
		
		if (type == 'F'){
			int pos = IT.getPos(b);
			IT.upd(1, n, 1, pos, pos + a - 1, 1);
			pair <int, int> get1 = IT.getMax(1, n, 1, 1, pos + a - 1);
			pair <int, int> get2 = IT.getMin(1, n, 1, pos + a, n); 
		
		
			if (get1.first > get2.first){
				// (pos + a - 1 - MaxCnt + 1) -> (pos + a - 1) || (pos + a) -> (pos + a + szMin - 1)	

				IT.transfer(pos + a - 1 - get1.second + 1, pos + a - 1, pos + a + get2.second- 1);
		 
				
			}	
		}
		
		if (type == 'C'){
			int pos2 = IT.getPos(b + 1);
			int pos1 = IT.getPos(a);
		
			cout << pos2 - pos1<<endl;
			
		}
		
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10