oj.uz

Submission #160473

# Submission time Handle Problem Language Result Execution time Memory
160473 2019-10-27T14:39:07 Z luciocf Growing Trees (BOI11_grow) C++14
0 / 100
 274 ms 4320 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]) 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 || l > r) 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) return (tree[0][node] >= v ? l : 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) return (tree[0][node] <= v ? l : -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);

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

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

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

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

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:100: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:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
grow.cpp:114: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 3836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 2296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 3816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 3932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 274 ms 3972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 138 ms 3952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 4320 KB Output isn't correct