oj.uz

Submission #762593

# Submission time Handle Problem Language Result Execution time Memory
762593 2023-06-21T14:25:34 Z Dzadzo Growing Trees (BOI11_grow) C++14
100 / 100
 767 ms 9004 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 || 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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 7268 KB Output is correct
2 Correct 628 ms 8832 KB Output is correct
3 Correct 189 ms 8728 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 11 ms 436 KB Output is correct
3 Correct 13 ms 472 KB Output is correct
4 Correct 7 ms 444 KB Output is correct
5 Correct 310 ms 1664 KB Output is correct
6 Correct 413 ms 1928 KB Output is correct
7 Correct 23 ms 816 KB Output is correct
8 Correct 195 ms 1532 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 1040 KB Output is correct
2 Correct 371 ms 2144 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 254 ms 1692 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 1244 KB Output is correct
2 Correct 418 ms 2020 KB Output is correct
3 Correct 37 ms 852 KB Output is correct
4 Correct 402 ms 2060 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 4044 KB Output is correct
2 Correct 591 ms 8408 KB Output is correct
3 Correct 100 ms 2360 KB Output is correct
4 Correct 170 ms 8356 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 7152 KB Output is correct
2 Correct 626 ms 7260 KB Output is correct
3 Correct 199 ms 8444 KB Output is correct
4 Correct 96 ms 2316 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 7292 KB Output is correct
2 Correct 367 ms 8428 KB Output is correct
3 Correct 195 ms 8716 KB Output is correct
4 Correct 94 ms 2328 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 7240 KB Output is correct
2 Correct 569 ms 7160 KB Output is correct
3 Correct 92 ms 7928 KB Output is correct
4 Correct 326 ms 8264 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 7572 KB Output is correct
2 Correct 607 ms 8892 KB Output is correct
3 Correct 767 ms 9004 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 7716 KB Output is correct