oj.uz

Submission #762567

# Submission time Handle Problem Language Result Execution time Memory
762567 2023-06-21T13:49:45 Z Dzadzo Growing Trees (BOI11_grow) C++14
0 / 100
 1000 ms 14292 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+11];
		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);
	return merge(query(v*2,tl,tm,l,min(r,tm)),query(v*2+1,tm+1,tr,max(tm+1,l),r));
}
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:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main(){
      | ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 14160 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 1260 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 3884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 7000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 6452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 14292 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 7088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 7552 KB Time limit exceeded
2 Halted 0 ms 0 KB -