oj.uz

Submission #762587

# Submission time Handle Problem Language Result Execution time Memory
762587 2023-06-21T14:15:36 Z Dzadzo Growing Trees (BOI11_grow) C++14
10 / 100
 642 ms 7680 KB 
#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)cout<<"0 \n"; else{
				if (ind1==-1)ind1=n;
				cout<<ind1-ind2+1<<"\n";
			}
			
		}
	}
}

Compilation message

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

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 7148 KB Output is correct
2 Incorrect 618 ms 7312 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 7284 KB Output is correct
2 Incorrect 565 ms 7188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 7680 KB Output is correct