Karaev_Marik's blog

By Karaev_Marik, history, 9 years ago, In Russian

Привет Codeforces! Я попытался реализовать дерево отрезков для минимума... Вроде все компилируется, но при запуске программа аварийно завершается (например, при таком тесте n=6, l=3,r=6, a{1,2,3,4,5,6,7,8,9,10})... Помогите разобраться в чем проблема?... Ниже мой код

#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("input.txt");
ofstream fout("output.txt");

const int INF=(int)10e4;
const int Nmax=1000;
int a[Nmax],t[4*Nmax];
int n;


void build(int v,int l, int r){
	
	if(l==r)
		t[v]=a[l];
	else{
		
		int m=(l+r)/2;
		build(v*2,l,m);
		build(v*2+1,m+1,r);
		t[v]=min(t[2*v],t[2*v+1]);
	}	
}


int getmin(int v,int l,int r,int i,int j){
	
	if(l>r)
		return INF;
	if(l==i && j==r)
		return t[v];
	int m=(l+r)/2;
	int m1=getmin(2*v,l,m,i,min(j,m));
	int m2=getmin(2*v+1,m+1,r,max(m+1,i),j);
	return min(m1,m2);		
}

int main(){
	
	int l,r;
	fin >> n >> l >> r;
	for(int i=0;i<n;++i)
		fin >> a[i];
	
	build(1,0,n-1);
	
	fout << getmin(1,0,n-1,l,r);
	return 0;
	
}
  • Vote: I like it
  • +3
  • Vote: I do not like it