Chimic

#include <fstream>
#include <vector>
using namespace std;
vector <long long> Aint;
vector <pair <int,int>> Interval;

void Update(int nod,int st,int dr,long long val,int poz)
{
	if(st==dr)
	{
		Aint[nod]+=val;
		return;
	}
	int mij=st+dr>>1;
	if(poz<=mij)
		Update(nod<<1,st,mij,val,poz);
	else
        Update(nod<<1|1,mij+1,dr,val,poz);
	Aint[nod]=max(Aint[nod<<1],Aint[nod<<1|1]);
}

long long RangeQuerry(int nod,int st,int dr,int a,int b)
{
	if(a<=st&&dr<=b)
		return Aint[nod];
	int mij=st+dr>>1;
	long long MaxLeft=0;
	long long MaxRight=0;
	if(a<=mij)
		MaxLeft=RangeQuerry(nod<<1,st,mij,a,b);
	if(mij<b)
		MaxRight=RangeQuerry(nod<<1|1,mij+1,dr,a,b);
	return max(MaxLeft,MaxRight);
}

int main(int argc,char const *argv[])
{
	int n;
	ifstream f("chimic.in");
	f>>n;
	Aint.resize(n<<2);
	Interval.resize(n+1);
	fill(Aint.begin(),Aint.end(),0);
	for(int i=1;i<=n;++i)
	{
		int x;
		f>>x;
		Update(1,1,n,1LL*x,i);
	}
	for(int i=1;i<=n;++i)
		f>>Interval[i].first>>Interval[i].second;
    f.close();
	for(int i=n;i>=1;--i)
	{
		if(Interval[i].first==-1)
            continue;
		long long maxim=RangeQuerry(1,1,n,Interval[i].first,Interval[i].second);
		Update(1,1,n,maxim,i);
	}
	ofstream g("chimic.out");
	g<<Aint[1];
	g.close();
	return 0;
}