Submission #222933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
222933	2020-04-14T11:11:40 Z	Andrei_Cotor	Constellation 3 (JOI20_constellation3)	C++11	100 / 100	283 ms	40440 KB

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.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	14464 KB	Output is correct
2	Correct	14 ms	14592 KB	Output is correct
3	Correct	14 ms	14464 KB	Output is correct
4	Correct	17 ms	14464 KB	Output is correct
5	Correct	13 ms	14464 KB	Output is correct
6	Correct	13 ms	14464 KB	Output is correct
7	Correct	13 ms	14464 KB	Output is correct
8	Correct	13 ms	14464 KB	Output is correct
9	Correct	13 ms	14464 KB	Output is correct
10	Correct	13 ms	14464 KB	Output is correct
11	Correct	13 ms	14464 KB	Output is correct
12	Correct	13 ms	14464 KB	Output is correct
13	Correct	14 ms	14780 KB	Output is correct
14	Correct	13 ms	14592 KB	Output is correct
15	Correct	15 ms	14464 KB	Output is correct
16	Correct	13 ms	14464 KB	Output is correct
17	Correct	14 ms	14464 KB	Output is correct
18	Correct	16 ms	14464 KB	Output is correct
19	Correct	14 ms	14488 KB	Output is correct
20	Correct	14 ms	14464 KB	Output is correct
21	Correct	14 ms	14464 KB	Output is correct
22	Correct	16 ms	14464 KB	Output is correct

Subtask #2
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	14464 KB	Output is correct
2	Correct	14 ms	14592 KB	Output is correct
3	Correct	14 ms	14464 KB	Output is correct
4	Correct	17 ms	14464 KB	Output is correct
5	Correct	13 ms	14464 KB	Output is correct
6	Correct	13 ms	14464 KB	Output is correct
7	Correct	13 ms	14464 KB	Output is correct
8	Correct	13 ms	14464 KB	Output is correct
9	Correct	13 ms	14464 KB	Output is correct
10	Correct	13 ms	14464 KB	Output is correct
11	Correct	13 ms	14464 KB	Output is correct
12	Correct	13 ms	14464 KB	Output is correct
13	Correct	14 ms	14780 KB	Output is correct
14	Correct	13 ms	14592 KB	Output is correct
15	Correct	15 ms	14464 KB	Output is correct
16	Correct	13 ms	14464 KB	Output is correct
17	Correct	14 ms	14464 KB	Output is correct
18	Correct	16 ms	14464 KB	Output is correct
19	Correct	14 ms	14488 KB	Output is correct
20	Correct	14 ms	14464 KB	Output is correct
21	Correct	14 ms	14464 KB	Output is correct
22	Correct	16 ms	14464 KB	Output is correct
23	Correct	15 ms	14720 KB	Output is correct
24	Correct	16 ms	14720 KB	Output is correct
25	Correct	15 ms	14720 KB	Output is correct
26	Correct	19 ms	14720 KB	Output is correct
27	Correct	16 ms	14720 KB	Output is correct
28	Correct	15 ms	14720 KB	Output is correct
29	Correct	15 ms	14720 KB	Output is correct
30	Correct	15 ms	14720 KB	Output is correct
31	Correct	20 ms	14640 KB	Output is correct
32	Correct	14 ms	14720 KB	Output is correct
33	Correct	15 ms	14720 KB	Output is correct
34	Correct	15 ms	14848 KB	Output is correct
35	Correct	15 ms	14720 KB	Output is correct
36	Correct	17 ms	14720 KB	Output is correct
37	Correct	15 ms	14720 KB	Output is correct
38	Correct	15 ms	14720 KB	Output is correct
39	Correct	16 ms	14696 KB	Output is correct
40	Correct	15 ms	14720 KB	Output is correct
41	Correct	14 ms	14720 KB	Output is correct
42	Correct	15 ms	14720 KB	Output is correct
43	Correct	15 ms	14720 KB	Output is correct
44	Correct	14 ms	14720 KB	Output is correct

Subtask #3
65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	14464 KB	Output is correct
2	Correct	14 ms	14592 KB	Output is correct
3	Correct	14 ms	14464 KB	Output is correct
4	Correct	17 ms	14464 KB	Output is correct
5	Correct	13 ms	14464 KB	Output is correct
6	Correct	13 ms	14464 KB	Output is correct
7	Correct	13 ms	14464 KB	Output is correct
8	Correct	13 ms	14464 KB	Output is correct
9	Correct	13 ms	14464 KB	Output is correct
10	Correct	13 ms	14464 KB	Output is correct
11	Correct	13 ms	14464 KB	Output is correct
12	Correct	13 ms	14464 KB	Output is correct
13	Correct	14 ms	14780 KB	Output is correct
14	Correct	13 ms	14592 KB	Output is correct
15	Correct	15 ms	14464 KB	Output is correct
16	Correct	13 ms	14464 KB	Output is correct
17	Correct	14 ms	14464 KB	Output is correct
18	Correct	16 ms	14464 KB	Output is correct
19	Correct	14 ms	14488 KB	Output is correct
20	Correct	14 ms	14464 KB	Output is correct
21	Correct	14 ms	14464 KB	Output is correct
22	Correct	16 ms	14464 KB	Output is correct
23	Correct	15 ms	14720 KB	Output is correct
24	Correct	16 ms	14720 KB	Output is correct
25	Correct	15 ms	14720 KB	Output is correct
26	Correct	19 ms	14720 KB	Output is correct
27	Correct	16 ms	14720 KB	Output is correct
28	Correct	15 ms	14720 KB	Output is correct
29	Correct	15 ms	14720 KB	Output is correct
30	Correct	15 ms	14720 KB	Output is correct
31	Correct	20 ms	14640 KB	Output is correct
32	Correct	14 ms	14720 KB	Output is correct
33	Correct	15 ms	14720 KB	Output is correct
34	Correct	15 ms	14848 KB	Output is correct
35	Correct	15 ms	14720 KB	Output is correct
36	Correct	17 ms	14720 KB	Output is correct
37	Correct	15 ms	14720 KB	Output is correct
38	Correct	15 ms	14720 KB	Output is correct
39	Correct	16 ms	14696 KB	Output is correct
40	Correct	15 ms	14720 KB	Output is correct
41	Correct	14 ms	14720 KB	Output is correct
42	Correct	15 ms	14720 KB	Output is correct
43	Correct	15 ms	14720 KB	Output is correct
44	Correct	14 ms	14720 KB	Output is correct
45	Correct	271 ms	38196 KB	Output is correct
46	Correct	260 ms	37868 KB	Output is correct
47	Correct	264 ms	38124 KB	Output is correct
48	Correct	277 ms	37896 KB	Output is correct
49	Correct	250 ms	37736 KB	Output is correct
50	Correct	252 ms	37484 KB	Output is correct
51	Correct	262 ms	37740 KB	Output is correct
52	Correct	267 ms	38252 KB	Output is correct
53	Correct	283 ms	38172 KB	Output is correct
54	Correct	220 ms	40440 KB	Output is correct
55	Correct	215 ms	40288 KB	Output is correct
56	Correct	237 ms	39740 KB	Output is correct
57	Correct	216 ms	39928 KB	Output is correct
58	Correct	196 ms	34168 KB	Output is correct
59	Correct	208 ms	34300 KB	Output is correct
60	Correct	172 ms	37752 KB	Output is correct
61	Correct	159 ms	33716 KB	Output is correct
62	Correct	233 ms	37624 KB	Output is correct
63	Correct	165 ms	33312 KB	Output is correct
64	Correct	159 ms	33492 KB	Output is correct
65	Correct	212 ms	37240 KB	Output is correct
66	Correct	159 ms	33520 KB	Output is correct

Submission #222933

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 21.0 / 21.0

Subtask #3 65.0 / 65.0

Subtask #1
14.0 / 14.0

Subtask #2
21.0 / 21.0

Subtask #3
65.0 / 65.0