Submission #388413

#	Time	Username	Problem	Language	Result	Execution time	Memory
388413		ogibogi2004	Constellation 3 (JOI20_constellation3)	C++14	0 / 100	14 ms	22256 KiB

constellation3

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
int n,m,sum;
struct star
{
	int x,y,c;
	bool operator<(star const& other)const
	{
		return make_pair(y,c)>make_pair(other.y,other.c);
	}
};
struct DSU
{
	int par[MAXN],sz[MAXN];
	void init()
	{
		for(int i=1;i<MAXN;i++)
		{
			par[i]=i;sz[i]=1;
		}
	}
	int getRoot(int u)
	{
		if(par[u]==u)return u;
		return par[u]=getRoot(par[u]);
	}
	void join(int p,int q)
	{
		if(sz[p]>=sz[q])
		{
			par[q]=p;
			sz[p]+=sz[q];
		}
		else
		{
			par[p]=q;
			sz[q]+=sz[p];
		}
	}
}dsu;
struct segment_tree
{
	int t[4*MAXN];
	int lazy[4*MAXN];
	void init()
	{
		memset(t,0,sizeof(t));
		memset(lazy,0,sizeof(lazy));
	}
	void push(int l,int r,int idx)
	{
		t[idx]+=lazy[idx];
		if(l!=r)
		{
			lazy[idx*2]+=lazy[idx];
			lazy[idx*2+1]+=lazy[idx];
		}
		lazy[idx]=0;
	}
	void update(int l,int r,int idx,int ql,int qr,int val)
	{
		push(l,r,idx);
		if(l>qr||r<ql)return;
		if(l>=ql&&r<=qr)
		{
			lazy[idx]+=val;
			push(l,r,idx);
			return;
		}
		int mid=(l+r)/2;
		update(l,mid,idx*2,ql,qr,val);
		update(mid+1,r,idx*2+1,ql,qr,val);
		t[idx]=max(t[idx*2],t[idx*2+1]);
	}
	int query(int l,int r,int idx,int ql,int qr)
	{
		push(l,r,idx);
		if(l>qr||r<ql)return 0;
		if(l>=ql&&r<=qr)
		{
			return t[idx];
		}
		int mid=(l+r)/2;
		return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
	}
	void update(int l,int r,int val)
	{
		update(1,n,1,l,r,val);
	}
	int query(int l,int r)
	{
		return query(1,n,1,l,r);
	}
}tree;
int a[MAXN];
vector<star>starsx[MAXN];
vector<star>starsy[MAXN];
vector<int>jp[MAXN];
int pr[MAXN];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	dsu.init();tree.init();
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		if(i>1)jp[max(a[i],a[i-1])].push_back(i);
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,c;
		cin>>x>>y>>c;sum+=c;
		starsx[x].push_back({x,y,c});
	}
	for(int i=1;i<=n;i++)
	{
		vector<star>v1;
		sort(starsx[i].begin(),starsx[i].end());
		for(int j=0;j<starsx[i].size();j++)
		{
			while(!v1.size()==0&&v1.back().c<starsx[i][j].c)
			{
				v1.pop_back();
			}
			v1.push_back(starsx[i][j]);
		}
		for(auto xd:v1)
		{
			starsy[xd.y].push_back(xd);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(auto xd:starsy[i])
		{
			tree.update(xd.x,xd.x,xd.c-pr[xd.x]);
			pr[xd.x]=xd.c;
		}
		for(auto xd:jp[i])
		{
			int e1=xd,e2=xd-1;
			int r1=dsu.getRoot(e1);
			int r2=dsu.getRoot(e2);
			int mxl=tree.query(e2-dsu.sz[r2]+1,e2);
			int mxr=tree.query(e1,e1+dsu.sz[r1]-1);
			tree.update(e2-dsu.sz[r2]+1,e2,mxr);
			tree.update(e1,e1+dsu.sz[r1]-1,mxl);
			dsu.join(r1,r2);
		}
	}
	cout<<sum-tree.query(1,n)<<endl;
return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:124:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<star>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   for(int j=0;j<starsx[i].size();j++)
      |               ~^~~~~~~~~~~~~~~~~

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