Submission #222933

#	Time	Username	Problem	Language	Result	Execution time	Memory
222933		Andrei_Cotor	Constellation 3 (JOI20_constellation3)	C++11	100 / 100	283 ms	40440 KiB

constellation3

//daca iau o stea nu voi putea lua o stea de deasupra ei cu x in intrevalul de cladiri in care se afla prima stea
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct star
{
	int st,dr,center,ind;
};

vector<int> Buildings[200005];
vector<pair<int,int> > Stars[200005];
vector<star> Interv[200005];
int Cost[200005];
int P[200005],Sz[200005],L[200005],R[200005];

int parent(int x)
{
	int _x=x;
	while(P[x]!=0)
		x=P[x];

	while(P[_x]!=0)
	{
		int aux=P[_x];
		P[_x]=x;
		_x=aux;
	}
	return x;
}

void unite(int x, int y)
{
	x=parent(x);
	y=parent(y);

	if(Sz[x]<Sz[y])
		swap(x,y);

	if(Sz[y]==0 || x==y)
		return;

	Sz[x]+=Sz[y];
	P[y]=x;
	L[x]=min(L[x],L[y]);
	R[x]=max(R[x],R[y]);
}

int n;
long long Fst[200005],Fdr[200005];

void updatest(int poz, long long val)
{
	while(poz<=n)
	{
		Fst[poz]+=val;
		poz=poz+(poz&(poz^(poz-1)));
	}
}

void updatedr(int poz, long long val)
{
	while(poz>=1)
	{
		Fdr[poz]+=val;
		poz=poz-(poz&(poz^(poz-1)));
	}
}

void update(int st, int dr, long long val)
{
	updatest(dr,val);
	updatedr(st,val);
}

long long getvalst(int poz)
{
	long long rez=0;
	while(poz>=1)
	{
		rez=rez+Fst[poz];
		poz=poz-(poz&(poz^(poz-1)));
	}
	return rez;
}

long long queryst(int st, int dr)
{
	return getvalst(dr)-getvalst(st-1);
}

long long getvaldr(int poz)
{
	long long rez=0;
	while(poz<=n)
	{
		rez=rez+Fdr[poz];
		poz=poz+(poz&(poz^(poz-1)));
	}
	return rez;
}

long long querydr(int st, int dr)
{
	return getvaldr(st)-getvaldr(dr+1);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin>>n;
	for(int i=1; i<=n; i++)
	{
		int h;
		cin>>h;

		Buildings[h].push_back(i);
	}

	int m;
	cin>>m;
	long long sum=0;
	for(int i=1; i<=m; i++)
	{
		int x,y;
		cin>>x>>y>>Cost[i];

		Stars[y].push_back({x,i});
		sum+=Cost[i];
	}

	for(int i=1; i<=n; i++)
	{
		for(auto star:Stars[i])
		{
			int pa=parent(star.first);
			int st=L[pa];
			int dr=R[pa];

			Interv[dr-st].push_back({st,dr,star.first,star.second});
		}

		for(auto building:Buildings[i])
		{
			Sz[building]=1;
			L[building]=R[building]=building;

			unite(building-1,building);
			unite(building,building+1);
		}
	}

	for(int i=0; i<=n; i++)
	{
		for(auto interv:Interv[i])
		{
			long long cr=querydr(interv.st,interv.dr);
			long long dp=Cost[interv.ind]+queryst(interv.st,interv.center-1)+querydr(interv.center+1,interv.dr);

			if(dp>cr)
				update(interv.st,interv.dr,dp-cr);
		}
	}

	cout<<sum-querydr(1,n)<<"\n";
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65