oj.uz

답안 #860098

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
860098 2023-10-11T16:01:32 Z ZeroCool Growing Trees (BOI11_grow) C++14
100 / 100
 736 ms 10348 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 8532 KB Output is correct
2 Correct 531 ms 8904 KB Output is correct
3 Correct 177 ms 8496 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 8 ms 636 KB Output is correct
3 Correct 9 ms 600 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 232 ms 1728 KB Output is correct
6 Correct 290 ms 2088 KB Output is correct
7 Correct 19 ms 708 KB Output is correct
8 Correct 163 ms 1472 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 2268 KB Output is correct
2 Correct 293 ms 2256 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 195 ms 1884 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 2536 KB Output is correct
2 Correct 317 ms 2136 KB Output is correct
3 Correct 33 ms 1116 KB Output is correct
4 Correct 286 ms 2388 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 351 ms 6480 KB Output is correct
2 Correct 506 ms 7752 KB Output is correct
3 Correct 70 ms 2140 KB Output is correct
4 Correct 140 ms 7252 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 456 ms 7256 KB Output is correct
2 Correct 511 ms 8008 KB Output is correct
3 Correct 172 ms 7556 KB Output is correct
4 Correct 71 ms 2384 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 7852 KB Output is correct
2 Correct 360 ms 8540 KB Output is correct
3 Correct 169 ms 8400 KB Output is correct
4 Correct 78 ms 2136 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 538 ms 8900 KB Output is correct
2 Correct 508 ms 7784 KB Output is correct
3 Correct 85 ms 8788 KB Output is correct
4 Correct 320 ms 8532 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 449 ms 8532 KB Output is correct
2 Correct 518 ms 8764 KB Output is correct
3 Correct 736 ms 9968 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 432 ms 10348 KB Output is correct