Submission #762593

#	Time	Username	Problem	Language	Result	Execution time	Memory
762593		Dzadzo	Growing Trees (BOI11_grow)	C++14	100 / 100	767 ms	9004 KiB

grow

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;
struct node{
	int mx,mn;
};
node t[400001];
int L[400001];

node new_val(int v){
	node res;
	res.mn=res.mx=v;
	return res;
}
node merge(node a,node b){
	node res;
	res.mn=min(a.mn,b.mn);
	res.mx=max(a.mx,b.mx);
	return res;
}
void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = new_val(a[tl]);
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = merge(t[v*2],t[v*2+1]);
    }
}
void push(int v){
	L[v*2]+=L[v];
	L[v*2+1]+=L[v];
	L[v]=0;
	
}
void update (int v,int tl,int tr,int l,int r){
	if (l>r)return;
	if (l==tl && tr==r)L[v]++;else{
		push(v);
		int tm=(tl+tr)/2;
		update(v*2,tl,tm,l,min(r,tm));
		update(v*2+1,tm+1,tr,max(l,tm+1),r);
		node res1,res2;
		res1.mn=t[v*2].mn+L[v*2];
		res1.mx=t[v*2].mn+L[v*2];
		res2.mn=t[v*2+1].mx+L[v*2+1];
		res2.mx=t[v*2+1].mx+L[v*2+1];
		t[v]=merge(res1,res2);
	}
}
node query(int v,int tl,int tr,int l,int r){
	if (l>r){
		node res;
		res.mx=-1;
		res.mn=INT_MAX;
		return res;
	}
	if (l==tl && r==tr){
		node res;
		res.mx=t[v].mx+L[v];
		res.mn=t[v].mn+L[v];
		return res;
	}
	int tm=(tl+tr)/2;
	push(v);
	node ans;
	ans = merge(query(v*2,tl,tm,l,min(r,tm)),query(v*2+1,tm+1,tr,max(tm+1,l),r));
	node res1,res2;
	res1.mn=t[v*2].mn+L[v*2];
	res1.mx=t[v*2].mn+L[v*2];
	res2.mn=t[v*2+1].mx+L[v*2+1];
	res2.mx=t[v*2+1].mx+L[v*2+1];
	t[v]=merge(res1,res2);
	return ans;
}
int askL (int l,int r ,int val){
	if (l>r)return -1;
	if (query(1,1,n,l,r).mx<val)return -1;
	if (l==r)return l;
	int m=(l+r)/2;
	int check= askL(l,m,val);
	if (check!=-1)return check;
	return askL(m+1,r,val);
}
int askR (int l,int r ,int val){
	if (l>r)return -1;
	if (query(1,1,n,l,r).mn>val)return -1;
	if (l==r)return l;
	int m=(l+r)/2;
	int check= askR(m+1,r,val);
	if (check!=-1)return check;
	return askR(l,m,val);
}
main(){
	int m;
	cin>>n>>m;
	int a[n+1];
	for (int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	build(a,1,1,n);
	while (m--){
		char c;
		cin>>c;
		if (c=='F'){
			int l,h;
			cin>>l>>h;
			int ind=askL(1,n,h);
			if (ind+l-1>=n){
				update(1,1,n,ind,n);
				continue;
			}
			if (ind==-1)continue;
			int Ival=query(1,1,n,ind,ind).mn;
			int Fval=query(1,1,n,ind+l-1,ind+l-1).mn;
			if (Ival!=Fval){
				int i=askL(1,n,Fval);
				update(1,1,n,ind,i-1);
				l-=i-ind;
			}
			
			int w=askR(1,n,Fval);
			update(1,1,n,w-l+1,w);
		}else{
			int h1,h2;
			cin>>h1>>h2;
			int ind1=askR(1,n,h2),ind2=askL(1,n,h1);
			if (ind2==-1 || query(1,1,n,1,n).mn>h2 || query(1,1,n,1,n).mx<h1)cout<<"0 \n"; else{
				if (ind1==-1)ind1=n;
				cout<<ind1-ind2+1<<"\n";
			}
			
		}
	}
}

Compilation message (stderr)

grow.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   97 | main(){
      | ^~~~

• 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