Submission #361468

#	Time	Username	Problem	Language	Result	Execution time	Memory
361468		pure_mem	Growing Trees (BOI11_grow)	C++14	100 / 100	920 ms	3256 KiB

grow

#pragma GCC optimize("Ofast")

#include <cstdio>
#include <algorithm>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 3;

int n, q, a[N], t[N * 4], tt[N * 4];

void build(int v, int tl, int tr){
	if(tl == tr){
		t[v] = a[tl];
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm), build(v * 2 + 1, tm + 1, tr);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void push(int v){
	if(tt[v] == 0)
		return;
	t[v * 2] += tt[v], t[v * 2 + 1] += tt[v];
	tt[v * 2] += tt[v], tt[v * 2 + 1] += tt[v], tt[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, int val){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		t[v] += val, tt[v] += val;
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, val), upd(v * 2 + 1, tm + 1, tr, l, r, val);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int get(int v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return 0;
	if(tl >= l && tr <= r)
		return t[v];
	push(v);
	int tm = (tl + tr) / 2;
	return max(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
}
int get_pos(int val){
	int tl = 1, tr = n;
	while(tl <= tr){
		int tm = (tl + tr) / 2;
		if(get(1, 1, n, 1, tm) >= val)
			tr = tm - 1;
		else
			tl = tm + 1;
	}
	return tr + 1;
}

int main () {
	scanf("%d %d\n", &n, &q);
	for(int i = 1;i <= n;i++)
		scanf("%d", a + i);
	scanf("\n"), sort(a + 1, a + n + 1);
	build(1, 1, n);
	for(;q--;){
		char tc;
		int l, r;
		scanf("%c %d %d\n", &tc, &l, &r);
		if(tc == 'F'){
			int tmp = get_pos(r);
			if(tmp + l - 1 >= n){
				upd(1, 1, n, tmp, n, 1);
				continue;
			}		
			int pet = get(1, 1, n, tmp, tmp + l - 1);
			int tmpL = get_pos(pet);
			int tmpR = get_pos(pet + 1) - 1;
			upd(1, 1, n, tmp, tmpL - 1, 1);
			tmpL = tmpR - ((tmp + l - 1) - tmpL + 1) + 1;
			upd(1, 1, n, tmpL, tmpR, 1);
		}
		else{
			printf("%d\n", get_pos(r + 1) - get_pos(l));
		}
	}
}

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  scanf("%d %d\n", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
grow.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |   scanf("%d", a + i);
      |   ~~~~~^~~~~~~~~~~~~
grow.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("\n"), sort(a + 1, a + n + 1);
      |  ~~~~~^~~~~~
grow.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |   scanf("%c %d %d\n", &tc, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10