Submission #105926

#	Time	Username	Problem	Language	Result	Execution time	Memory
105926		asifthegreat	Growing Trees (BOI11_grow)	C++14	0 / 100	154 ms	6136 KiB

grow

#include <bits/stdc++.h>
//#define int long long 
//#define double long double 
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define debug(a) cout << #a << " = " << a << endl;
#define keepUnique(a) sort(all(a));a.erase(unique(all(a)),a.end())
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

const int N = 200005;

int n,m,ara[N];
pii tree[N*4+12];
int lazy[N*4+12];

void build(int at,int L,int R){
	if(L == R){
		tree[at] = {ara[L],ara[R]};
		return;
	}
	int mid = (L+R)>>1;
	build(at<<1,L,mid);
	build((at<<1)+1,mid+1,R);
	tree[at].first = min(tree[at<<1].first,tree[(at<<1)+1].first);
	tree[at].second = max(tree[at<<1].second,tree[(at<<1)+1].second);
}
void pushdown(int at,int L,int R){
	int lc = at*2;
	int rc = at*2+1;
	lazy[lc] = lazy[at];
	lazy[rc] = lazy[at];
	tree[lc].first+=lazy[at];
	tree[rc].first+=lazy[at];
	tree[lc].second += lazy[at];
	tree[rc].second += lazy[at];
	lazy[at] = 0;
}
void update(int at,int L,int R,int l,int r){
	if(l > r)return;
	if(L > r or R < l)return;
	if(l <= L and R <= r){
		tree[at].first++;
		tree[at].second++;
		lazy[at]++;
		return;
	}
	if(lazy[at])pushdown(at,L,R);
	int mid = (L+R)>>1;
	update(at<<1,L,mid,l,r);
	update((at<<1)+1,mid+1,R,l,r);

	tree[at].first = min(tree[at<<1].first,tree[(at<<1)+1].first);
	tree[at].second = max(tree[at<<1].second,tree[(at<<1)+1].second);
}

int lower(int at,int L,int R,int num){
	// num er theke boro ba shoman shob theke choto number er index dibe..
	if(L == R){
		if(tree[L].first < num)return L+1;
		return L;
	}
	if(lazy[at])pushdown(at,L,R);
	int mid = (L+R)>>1;
	if(tree[at*2].second >= num)lower(at*2,L,mid,num);
	else lower(at*2+1,mid+1,R,num);
}
int upper(int at,int L,int R,int num)
{
	// num er theke choto ba shoman shob theke boro number er index dibe.. 
	if(L == R){
		//if(tree[L].first )
		return L;
	}
	if(lazy[at])pushdown(at,L,R);
	int mid = (L+R)>>1;
	if(tree[at*2+1].first <= num)return upper(at*2+1,mid+1,R,num);
	else return upper(at*2,L,mid,num);
}	
int find_kth(int at,int L,int R,int k)
{
	if(L == R)return tree[at].first;
	if(lazy[at])pushdown(at,L,R);
	int mid = (L+R)>>1;
	if(k <= mid)return find_kth(at<<1,L,mid,k);
	else return find_kth((at<<1)+1,mid+1,R,k);
}

int32_t main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i = 1; i <= n;i++){
		cin >> ara[i];
	}
	sort(ara+1,ara+1+n);
	build(1,1,n);
	char s[10];
	//update(1,1,n,1,n);
	//cout << tree[2].first << " " << tree[2].second << endl;
	//cout << find_kth(1,1,n,3) << endl;
	while(m--){
		scanf("%s",s);
		if(s[0] == 'F'){
			int hi,ci;
			scanf("%d %d",&ci,&hi);
			int ll = lower(1,1,n,hi);
			int rr = min(n,ll+ci-1);
			int kth = find_kth(1,1,n,rr);
			int left_expand = lower(1,1,n,kth);
			int right_expand = upper(1,1,n,kth);
			//debug(ll);
			//debug(rr);
			//debug(kth);
			//debug(left_expand);
			//debug(right_expand);

			// upd(ll,left_expand-1);
			// upd()
			//printf("ekta update gese [%d-%d]\n",ll,left_expand-1);
			update(1,1,n,ll,left_expand-1);
			int baki = left_expand-ll;
			baki = (rr-ll+1)-baki;

			update(1,1,n,right_expand-baki+1,right_expand);
			//printf("ekta update gese [%d-%d]\n",right_expand-baki+1,right_expand);

		}
		else{
			int a,b;
			scanf("%d%d",&a,&b);
			//debug(upper(1,1,n,b));
			//debug(lower(1,1,n,a));
			printf("%d\n",upper(1,1,n,b)-lower(1,1,n,a)+1);
		}
	}

	
	return 0;
}

Compilation message (stderr)

grow.cpp: In function 'int lower(int, int, int, int)':
grow.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
grow.cpp: In function 'int32_t main()':
grow.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
grow.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s);
   ~~~~~^~~~~~~~
grow.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&ci,&hi);
    ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:133:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d",&a,&b);
    ~~~~~^~~~~~~~~~~~~~

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