oj.uz

Submission #160479

# Submission time Handle Problem Language Result Execution time Memory
160479 2019-10-27T15:03:56 Z luciocf Growing Trees (BOI11_grow) C++14
100 / 100
 242 ms 5724 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int n;
int a[maxn];

int tree[2][4*maxn], lazy[4*maxn];

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[0][node] = tree[1][node] = a[l];
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	tree[0][node] = min(tree[0][2*node], tree[0][2*node+1]);
	tree[1][node] = max(tree[1][2*node], tree[1][2*node+1]); 
}

void flush(int node, int l, int r)
{
	if (!lazy[node] || l > r) return;

	if (l != r)
		lazy[2*node] += lazy[node], lazy[2*node+1] += lazy[node];

	tree[0][node] += lazy[node];
	tree[1][node] += lazy[node];
	lazy[node] = 0;
}

void upd(int node, int l, int r, int a, int b, int v)
{
	flush(node, l, r);
	if (l > b || r < a || a > b) return;

	if (l >= a && r <= b)
	{
		lazy[node] = v;
		flush(node, l, r);
		return;
	}

	int mid = (l+r)>>1;

	upd(2*node, l, mid, a, b, v); upd(2*node+1, mid+1, r, a, b, v);

	tree[0][node] = min(tree[0][2*node], tree[0][2*node+1]);
	tree[1][node] = max(tree[1][2*node], tree[1][2*node+1]); 
}

int findVal(int node, int l, int r, int pos)
{
	flush(node, l, r);
	if (l == r) return tree[0][node];

	int mid = (l+r)>>1;

	if (pos <= mid) return findVal(2*node, l, mid, pos);
	return findVal(2*node+1, mid+1, r, pos);
}

int findL(int node, int l, int r, int v)
{
	flush(node, l, r);
	if (l == r)
	{
		if (tree[0][node] >= v) return l;
		return n+1;
	}

	int mid = (l+r)>>1;

	flush(2*node, l, mid); flush(2*node+1, mid+1, r);

	if (tree[1][2*node] < v) return findL(2*node+1, mid+1, r, v);
	return findL(2*node, l, mid, v);
}

int findR(int node, int l, int r, int v)
{
	flush(node, l, r);
	if (l == r)
	{
		if (tree[0][node] <= v) return l;
		return -1;
	}

	int mid = (l+r)>>1;

	flush(2*node, l, mid); flush(2*node+1, mid+1, r);

	if (tree[0][2*node+1] > v) return findR(2*node, l, mid, v);
	return findR(2*node+1, mid+1, r, v);
}

int main(void)
{
	int q;
	scanf("%d %d", &n, &q);

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	sort(a+1, a+n+1);

	build(1, 1, n);

	for (int i = 1; i <= q; i++)
	{
		char op;
		int a, b;

		scanf(" %c %d %d", &op, &a, &b);

		if (op == 'F')
		{
			int l = findL(1, 1, n, b), r = min(n, l+a-1);

			if (l == n+1) continue;

			int val = findVal(1, 1, n, r);
			int l_val = findL(1, 1, n, val), r_val = findR(1, 1, n, val);

			assert(l_val <= r_val);

			upd(1, 1, n, l, l_val-1, 1);

			int resto = a-(l_val-l);
			upd(1, 1, n, max(l_val, r_val-resto+1), r_val, 1);
		}
		else
		{
			int l = findL(1, 1, n, a);
			int r = findR(1, 1, n, b);

			if (l > r) printf("0\n");
			else printf("%d\n", r-l+1);
		}
	}
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
grow.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %d", &op, &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 3960 KB Output is correct
2 Correct 182 ms 5680 KB Output is correct
3 Correct 187 ms 5548 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 4 ms 464 KB Output is correct
5 Correct 59 ms 1648 KB Output is correct
6 Correct 73 ms 1896 KB Output is correct
7 Correct 9 ms 632 KB Output is correct
8 Correct 47 ms 1400 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 992 KB Output is correct
2 Correct 78 ms 1976 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 55 ms 1528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 1048 KB Output is correct
2 Correct 81 ms 1940 KB Output is correct
3 Correct 16 ms 632 KB Output is correct
4 Correct 76 ms 2096 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 2296 KB Output is correct
2 Correct 187 ms 5080 KB Output is correct
3 Correct 33 ms 1628 KB Output is correct
4 Correct 147 ms 5152 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 3864 KB Output is correct
2 Correct 159 ms 5240 KB Output is correct
3 Correct 179 ms 5368 KB Output is correct
4 Correct 23 ms 1528 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 3936 KB Output is correct
2 Correct 118 ms 5112 KB Output is correct
3 Correct 179 ms 5368 KB Output is correct
4 Correct 22 ms 1528 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 4004 KB Output is correct
2 Correct 161 ms 5316 KB Output is correct
3 Correct 48 ms 4592 KB Output is correct
4 Correct 110 ms 4976 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 4088 KB Output is correct
2 Correct 158 ms 5624 KB Output is correct
3 Correct 242 ms 5724 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 4344 KB Output is correct