oj.uz

Submission #56144

# Submission time Handle Problem Language Result Execution time Memory
56144 2018-07-10T05:55:10 Z 윤교준(#1582) Growing Trees (BOI11_grow) C++11
100 / 100
 155 ms 2236 KB 
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const int MAXN = 200055;

struct BIT {
	int d[MAXN];
	void upd(int x, int r) {
		for(x += 5; x < MAXN; x += rb(x))
			d[x] += r;
	}
	int get(int x) {
		int r = 0; for(x += 5; x; x -= rb(x))
			r += d[x];
		return r;
	}
} bit;

int A[MAXN];

int N, Q;

int f(int x) {
	if(x < 1) return -INF;
	if(N < x) return INF;
	return A[x] + bit.get(x);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> Q;
	for(int i = 1; i <= N; i++) cin >> A[i];
	sort(A+1, A+N+1);

	for(char type; Q--;) {
		int a, b; cin >> type >> a >> b;
		if('F' == type) {
			if(f(N) < b || !a) continue;

			int l = 1;
			{
				int s = 1, e = N; for(int m; s < e;) {
					m = (s+e)/2;
					if(b <= f(m)) e = m;
					else s = m+1;
				}
				l = s;
			}

			int r = l+a-1, h = f(r), rl = r, rr = r;
			{
				int s = l, e = r; for(int m; s < e;) {
					m = (s+e)/2;
					if(f(m) < h) s = m+1;
					else e = m;
				}
				rl = s;
			}
			{
				int s = r, e = N; for(int m; s < e;) {
					m = (s+e+1)/2;
					if(h < f(m)) e = m-1;
					else s = m;
				}
				rr = s;
			}

			bit.upd(l, 1); bit.upd(rl, -1);

			int len = a - (rl - l);
			bit.upd(rr-len+1, 1); bit.upd(rr+1, -1);
		} else {
			if(b < f(1) || f(N) < a) {
				puts("0");
				continue;
			}
			int l = 1, r = N;
			{
				int s = 1, e = N; for(int m; s < e;) {
					m = (s+e)/2;
					if(a <= f(m)) e = m;
					else s = m+1;
				}
				l = s;
			}
			{
				int s = 1, e = N; for(int m; s < e;) {
					m = (s+e+1)/2;
					if(b < f(m)) e = m-1;
					else s = m;
				}
				r = s;
			}
			printf("%d\n", max(0, r-l+1));
		}
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 1656 KB Output is correct
2 Correct 151 ms 1708 KB Output is correct
3 Correct 92 ms 1708 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1708 KB Output is correct
2 Correct 5 ms 1708 KB Output is correct
3 Correct 6 ms 1708 KB Output is correct
4 Correct 5 ms 1708 KB Output is correct
5 Correct 80 ms 1708 KB Output is correct
6 Correct 83 ms 1708 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 36 ms 1708 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 1708 KB Output is correct
2 Correct 88 ms 1708 KB Output is correct
3 Correct 4 ms 1708 KB Output is correct
4 Correct 42 ms 1708 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1708 KB Output is correct
2 Correct 90 ms 1708 KB Output is correct
3 Correct 9 ms 1708 KB Output is correct
4 Correct 80 ms 1708 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 1708 KB Output is correct
2 Correct 153 ms 1708 KB Output is correct
3 Correct 34 ms 1708 KB Output is correct
4 Correct 80 ms 1708 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 1724 KB Output is correct
2 Correct 146 ms 1768 KB Output is correct
3 Correct 98 ms 1768 KB Output is correct
4 Correct 27 ms 1768 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 1852 KB Output is correct
2 Correct 95 ms 1908 KB Output is correct
3 Correct 83 ms 1908 KB Output is correct
4 Correct 25 ms 1908 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 1908 KB Output is correct
2 Correct 137 ms 1908 KB Output is correct
3 Correct 42 ms 1908 KB Output is correct
4 Correct 101 ms 1908 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 1908 KB Output is correct
2 Correct 148 ms 1908 KB Output is correct
3 Correct 144 ms 1908 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 2236 KB Output is correct