Submission #1044922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044922		hiuwsss	Growing Trees (BOI11_grow)	C++14	100 / 100	95 ms	10900 KiB

grow

#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 (stderr)

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