oj.uz

답안 #490472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490472 2021-11-27T15:45:09 Z BackNoob Growing Trees (BOI11_grow) C++14
10 / 100
 112 ms 5048 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);

			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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 3920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 2 ms 328 KB Output is correct
5 Correct 36 ms 1456 KB Output is correct
6 Incorrect 41 ms 1724 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 1632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 1700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 53 ms 2580 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 73 ms 3796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 3780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 4348 KB Output is correct
2 Incorrect 104 ms 3972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 4084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

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