oj.uz

Submission #160477

# Submission time Handle Problem Language Result Execution time Memory
160477 2019-10-27T14:48:08 Z luciocf Growing Trees (BOI11_grow) C++14
0 / 100
 181 ms 4344 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 || 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)
	{
		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);

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

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 3832 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 380 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 66 ms 884 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 800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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