제출 #860098

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
860098		ZeroCool	Growing Trees (BOI11_grow)	C++14	100 / 100	736 ms	10348 KiB

grow

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

using ll = long long;
using ld = long double;
 
void solve(int T);
void pre();
 
const int N = 1e5 + 5;
const int M = 405;
const int SQRT = 500;
const int LOG = 20;
const int INF = 1e18;
const int MOD = 1e9+7;
const ld EPS = 1e-9;

void pre(){
	#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
	#endif
	
}

int32_t main(){
	pre();
	int tt = 1;
	//cin>>tt;
	for(int i = 1;i<=tt;i++){
		cerr<<"Case "<<i<<": "<<endl;
		solve(i);
	}
    return 0;
}

struct SegTree {
    int n;
    vector<int> v;
    vector<ll> tree;
    vector<ll> lazy;
 
    SegTree(vector<int> const &_v) {
        this->v = _v;
        n = v.size();
        tree.resize(4*n+5, 0);
        lazy.resize(4*n+5, 0);
    }
 
    void push(int u, int tl, int tr) {
        if(lazy[u] == 0) return ;
 
        tree[u] += (tr - tl + 1) * lazy[u];
 
        if(tl != tr) {
            lazy[2*u] += lazy[u];
            lazy[2*u+1] += lazy[u];
        }
 
        lazy[u] = 0;
    }
 
    void build(int u, int tl, int tr) {
        if(tl == tr) {
            tree[u] = v[tl];
        } else {
            int tm = (tl + tr) / 2;
            build(2*u, tl, tm);
            build(2*u+1, tm+1, tr);
            tree[u] = tree[2*u] + tree[2*u+1];
        }
    }
 
    void update(int u, int tl, int tr, int l, int r, int val) {
        push(u, tl, tr);
        if(tl > tr || l > tr || tl > r) return ;
 
        if(l <= tl && tr <= r) {
            lazy[u] += val;
            push(u, tl, tr);
            return ;
        }
 
        int tm = (tl + tr) / 2;
        update(2*u, tl, tm, l, r, val);
        update(2*u+1, tm+1, tr, l, r, val);
        tree[u] = tree[2*u] + tree[2*u+1];
    }
 
    ll query(int u, int tl, int tr, int pos) {
        if(tl > tr || tl > pos || pos > tr) return 0;
        push(u, tl, tr);
        if(tl == tr) return tree[u];
        int tm = (tl + tr) / 2;
        if(pos <= tm)
            return query(2*u, tl, tm, pos);
        return query(2*u+1, tm+1, tr, pos);
    }
 
    void update(int l, int r, int val) {
        update(1, 0, n-1, l, r, val);
    }
 
    ll query(int pos) {
        return query(1, 0, n-1, pos);
    }
};

int n;

int binS(int l,int r, function<bool(int)> f){
	int ans = n;
	while(l <= r){
		int mid = (l + r)/ 2;
		if(f(mid)){
			ans = mid;
			r = mid - 1;
		}else{
			l = mid + 1;
		}
	}

	return ans;
}

void solve(int T){
	cin>>n;
	int q;
	cin>>q;
	
	vector<int> A(n);
	for(int i = 0;i<n;i++)cin>>A[i];

	sort(all(A));
	SegTree sgt(A);
	sgt.build(1,0,n-1);

	while(q--){
		char t;
		cin>>t;
		if(t == 'F'){
			int c,h;
			cin>>c>>h;
			int ql = binS(0,n-1,[&](int x){
				return sgt.query(x) >= h;
			});

			int qr = ql + c - 1;
			if(qr >= n-1){
				sgt.update(ql,qr,1);
				continue;
			}
			int nl = binS(ql, n-1, [&](int x){
				return sgt.query(x) >= sgt.query(qr);
			});
			int nr = binS(nl, n-1, [&](int x){
				return sgt.query(x) > sgt.query(qr);
			}) - 1;

			sgt.update(ql, nl - 1, 1);
			sgt.update(nr - c + nl - ql + 1, nr, 1);
		}else{
			int a,b;
			cin>>a>>b;
			if(sgt.query(n-1) < a){
				cout<<0<<endl;
				continue;
			}
			int l = binS(0, n-1, [&](int x) {
                return sgt.query(x) >= a;
            });
 
            int r = binS(0, n-1, [&](int x) {
                return sgt.query(x) > b;
            });

			cout<< r- l <<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