oj.uz

Submission #56142

# Submission time Handle Problem Language Result Execution time Memory
56142 2018-07-10T05:52:54 Z 윤교준(#1582) Growing Trees (BOI11_grow) C++11
30 / 100
 102 ms 2308 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 = 100005;

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

int A[MAXN];

int N, Q;

int f(int x) { 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1912 KB Output is correct
2 Correct 4 ms 1912 KB Output is correct
3 Correct 8 ms 1912 KB Output is correct
4 Correct 4 ms 1912 KB Output is correct
5 Correct 80 ms 1912 KB Output is correct
6 Correct 81 ms 1912 KB Output is correct
7 Correct 7 ms 1912 KB Output is correct
8 Correct 29 ms 1912 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 1912 KB Output is correct
2 Correct 74 ms 1912 KB Output is correct
3 Correct 3 ms 1912 KB Output is correct
4 Correct 57 ms 1912 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2036 KB Output is correct
2 Correct 102 ms 2036 KB Output is correct
3 Correct 11 ms 2036 KB Output is correct
4 Correct 78 ms 2036 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 2148 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 2148 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 2148 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 2148 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 2308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 2308 KB Execution killed with signal 11 (could be triggered by violating memory limits)