oj.uz

Submission #1044922

# Submission time Handle Problem Language Result Execution time Memory
1044922 2024-08-05T14:36:40 Z hiuwsss Growing Trees (BOI11_grow) C++14
100 / 100
 95 ms 10900 KB 
#include <bits/stdc++.h>
using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> i) & 1LL)
#define ll long long

template<class T> bool minimize(T &x, const T &y) {
    return x > y ? x = y, 1 : 0;
}

template<class T> bool maximize(T &x, const T &y) {
    return x < y ? x = y, 1 : 0;
}

const int MAX = 2e5 + 5;

int n, q;
int h[MAX];
int minValue[4 * MAX], maxValue[4 * MAX];
int lazy[4 * MAX];

void build(int i, int l, int r) {
	if (l == r) {
		minValue[i] = maxValue[i] = h[l];
		return;
	}

	int u = i << 1, v = i << 1 | 1, m = (l + r) >> 1;
	build(u, l, m); build(v, m + 1, r);

	minValue[i] = min(minValue[u], minValue[v]);
	maxValue[i] = max(maxValue[u], maxValue[v]);
}

void setAll(int i, int value) {
	minValue[i] += value, maxValue[i] += value;
	lazy[i] += value;
}

void pushDown(int i) {
	int u = i << 1, v = i << 1 | 1;
	setAll(u, lazy[i]), setAll(v, lazy[i]);

	lazy[i] = 0;
}

void update(int i, int l, int r, int u, int v) {
	if (l > v || u > r) return;
	if (u <= l && r <= v) {
		setAll(i, 1);
		return;
	}

	pushDown(i);
	int m = (l + r) >> 1;
	update(i << 1, l, m, u, v);
	update(i << 1 | 1, m + 1, r, u, v);

	minValue[i] = min(minValue[i << 1], minValue[i << 1 | 1]);
	maxValue[i] = max(maxValue[i << 1], maxValue[i << 1 | 1]);
}

// Return first pos >= x.
int getFirst(int i, int l, int r, int x) {
	if (l == r) return maxValue[i] >= x ? l : l + 1;

	pushDown(i);
	int u = i << 1, v = i << 1 | 1, m = (l + r) >> 1;
	if (maxValue[u] >= x) return getFirst(u, l, m, x);
	else return getFirst(v, m + 1, r, x);
}

// Return last pos <= x
int getLast(int i, int l, int r, int x) {
	if (l == r) return minValue[i] <= x ? l : l - 1;

	pushDown(i);
	int u = i << 1, v = i << 1 | 1, m = (l + r) >> 1;
	if (minValue[v] <= x) return getLast(v, m + 1, r, x);
	else return getLast(u, l, m, x);
}

int getValue(int i, int l, int r, int pos) {
	if (l == r) return minValue[i];

	pushDown(i);
	int u = i << 1, v = i << 1 | 1, m = (l + r) >> 1;
	if (pos > m) return getValue(v, m + 1, r, pos);
	else return getValue(u, l, m, pos);
}

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

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

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

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

void updateQuery(int c, int h) {
	if (getValue(n) < h) return;

	int L = getFirst(h);

	if (L + c - 1 > n) {
		update(L, n);
		return;
	}

	int value = getValue(L + c - 1);
	int R = getLast(value);

	int r = L - 1;
	if (getValue(L) < value) r = getLast(value - 1);

	if (r >= L) update(L, r);
	update(R - (c - (r - L + 1)) + 1, R);
}

void answerQuery(int L, int R) {
	cout << getLast(R) - getFirst(L) + 1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    #define TASK ""
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

	cin >> n >> q;
	FOR(i, 1, n) cin >> h[i];

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

	char t; int L, R;
	while (q--) {
		cin >> t >> L >> R;
		if (t == 'F') updateQuery(L, R);
		if (t == 'C') answerQuery(L, R);
	}

    return (0 ^ 0);
}

//hiuwsss

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9308 KB Output is correct
2 Correct 70 ms 10900 KB Output is correct
3 Correct 80 ms 10616 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 22 ms 4688 KB Output is correct
6 Correct 29 ms 4952 KB Output is correct
7 Correct 3 ms 4444 KB Output is correct
8 Correct 14 ms 4740 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4956 KB Output is correct
2 Correct 27 ms 4952 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 16 ms 4700 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5088 KB Output is correct
2 Correct 27 ms 4820 KB Output is correct
3 Correct 6 ms 4444 KB Output is correct
4 Correct 26 ms 4924 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 9216 KB Output is correct
2 Correct 59 ms 10576 KB Output is correct
3 Correct 11 ms 9304 KB Output is correct
4 Correct 53 ms 10380 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 9052 KB Output is correct
2 Correct 56 ms 10564 KB Output is correct
3 Correct 67 ms 10580 KB Output is correct
4 Correct 8 ms 9304 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 9596 KB Output is correct
2 Correct 41 ms 10504 KB Output is correct
3 Correct 65 ms 10804 KB Output is correct
4 Correct 8 ms 9308 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 9296 KB Output is correct
2 Correct 64 ms 10324 KB Output is correct
3 Correct 17 ms 9820 KB Output is correct
4 Correct 43 ms 10324 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 9300 KB Output is correct
2 Correct 62 ms 10840 KB Output is correct
3 Correct 95 ms 10836 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 9556 KB Output is correct