oj.uz

Submission #490483

# Submission time Handle Problem Language Result Execution time Memory
490483 2021-11-27T15:50:50 Z BackNoob Growing Trees (BOI11_grow) C++14
100 / 100
 141 ms 4536 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1) 
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 3e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

int n , q;
int a[mxN];
int t[mxN * 4];
int lazy[mxN * 4];

void build(int v , int tl , int tr)
{
	if(tl == tr) t[v] = a[tl];
	else {
		int tm = (tl + tr) / 2;
		build(v * 2 , tl , tm);
		build(v * 2 + 1 , tm + 1 , tr);
		t[v] = max(t[v * 2] , t[v * 2 + 1]);
	}
}

void modify(int v)
{
	t[v * 2] += lazy[v];
	t[v * 2 + 1] += lazy[v];
	lazy[v * 2] += lazy[v];
	lazy[v * 2 + 1] += lazy[v];
	lazy[v] = 0;
}

void update(int v , int tl , int tr , int l , int r)
{
	if(l > r) return ;
	if(tl == l && tr == r) {
		t[v]++;
		lazy[v]++;
		return;
	}
	int tm = (tl + tr) / 2;
	modify(v);
	update(v * 2 , tl , tm , l , min(r , tm));
	update(v * 2 + 1 , tm + 1 , tr , max(l , tm + 1) , r);
	t[v] = max(t[v * 2] , t[v * 2 + 1]);
}

int findfst(int v , int tl , int tr , int x)
{
	if(t[v] < x) return n + 1;
	if(tl == tr) return tl;
	modify(v);
	int tm = (tl + tr) / 2;
	if(t[v * 2] >= x) return findfst(v * 2 , tl , tm , x);
	return findfst(v * 2 + 1 , tm + 1 , tr , x);
}

int getidx(int v , int tl , int tr , int pos)
{
	if(tl == tr && tl == pos) return t[v];
	modify(v);
	int tm = (tl + tr) / 2;
	if(pos <= tm) return getidx(v * 2 , tl , tm , pos);
	return getidx(v * 2 + 1 , tm + 1 , tr , pos);
}

int getidx(int pos)
{
	return getidx(1 , 1 , n , pos);
}

int findfst(int x)
{
	return findfst(1 , 1 , n , x);
}

void update(int l , int r)
{
	update(1 , 1 , n , l , r);
}

void solve()
{
	cin >> n >> q;
	for(int i = 1 ; i <= n ; i++) cin >> a[i];

	sort(a + 1 , a + 1 + n);	
	build(1 , 1 , n);

	while(q--) {
		char cmd;
		cin >> cmd;
		if(cmd == 'F') {
			int c , h;
			cin >> c >> h;
			int l1 = findfst(h);
			int r1 = min(n , l1 + c - 1);

			if(r1 == n) {
				update(l1 , r1);
				continue;
			}

			int val = getidx(r1);

			int r2 = findfst(val);

			update(l1 , r2 - 1);

			int r3 = findfst(val + 1);

			int re = c - max(0 , (r2 - 1 - l1 + 1));
			update(max(r2 , r3 - 1 - re + 1) , r3 - 1);
		}
		else {
			int l , r;
			cin >> l >> r;
			cout << findfst(r + 1) - 1 - findfst(l) + 1 << endl;
		}
	}

}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen(TASK".in" , "r" , stdin);
    // freopen(TASK".out" , "w" , stdout);
    
    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3012 KB Output is correct
2 Correct 106 ms 4408 KB Output is correct
3 Correct 39 ms 4348 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 2 ms 332 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 38 ms 768 KB Output is correct
6 Correct 46 ms 972 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 26 ms 1232 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 948 KB Output is correct
2 Correct 43 ms 1824 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 28 ms 1428 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 972 KB Output is correct
2 Correct 50 ms 1820 KB Output is correct
3 Correct 8 ms 588 KB Output is correct
4 Correct 44 ms 1788 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1868 KB Output is correct
2 Correct 86 ms 4076 KB Output is correct
3 Correct 12 ms 1240 KB Output is correct
4 Correct 41 ms 4028 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 2904 KB Output is correct
2 Correct 83 ms 4236 KB Output is correct
3 Correct 33 ms 4312 KB Output is correct
4 Correct 12 ms 1332 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3024 KB Output is correct
2 Correct 64 ms 3984 KB Output is correct
3 Correct 40 ms 4332 KB Output is correct
4 Correct 14 ms 1356 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 3056 KB Output is correct
2 Correct 83 ms 2924 KB Output is correct
3 Correct 24 ms 3484 KB Output is correct
4 Correct 69 ms 3864 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 3076 KB Output is correct
2 Correct 91 ms 4292 KB Output is correct
3 Correct 141 ms 4536 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3376 KB Output is correct