Submission #212257

#	Time	Username	Problem	Language	Result	Execution time	Memory
212257		zscoder	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	711 ms	47984 KiB

constellation3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

ll a[233333];
const ll INF = ll(1e18);
vector<ii> pty[222222];
vector<ii> ptx[222222];
vector<ll> Y[222222];

struct DSU
{
	ll S;
	
	struct node
	{
		ll p; 
		ll l,r;
	};
	vector<node> dsu;
	
	DSU(ll n)
	{
		S = n;
		for(ll i = 0; i < n; i++)
		{
			node tmp;
			tmp.p = i; 
			tmp.l=tmp.r=i;
			dsu.pb(tmp);
		}
	}
	
	void reset(ll n)
	{
		dsu.clear();
		S = n;
		for(ll i = 0; i < n; i++)
		{
			node tmp;
			tmp.p = i;
			tmp.l=tmp.r=i;
			dsu.pb(tmp);
		}
	}
	
	ll rt(ll u)
	{
		if(dsu[u].p == u) return u;
		dsu[u].p = rt(dsu[u].p);
		return dsu[u].p;
	}
	
	void merge(ll u, ll v)
	{
		u = rt(u); v = rt(v);
		if(u == v) return ;
		if(rand()&1) swap(u, v);
		dsu[v].p = u;
		dsu[u].l = min(dsu[u].l,dsu[v].l);
		dsu[u].r = max(dsu[u].r,dsu[v].r);
	}
	
	bool sameset(ll u, ll v)
	{
		if(rt(u) == rt(v)) return true;
		return false;
	}
};


class LazySegmentTree {
private:
	int size_;
	vector<long long> v, lazy;
	void update(int a, int b, long long x, int k, int l, int r) {
		push(k, l, r);
		if (r <= a || b <= l) return;
		if (a <= l && r <= b) {
			lazy[k] += x;
			push(k, l, r);
		}
		else {
			update(a, b, x, k * 2, l, (l + r) >> 1);
			update(a, b, x, k * 2 + 1, (l + r) >> 1, r);
			v[k] = merge(v[k * 2], v[k * 2 + 1]);
		}
	}
	long long query(int a, int b, int k, int l, int r) {
		push(k, l, r);
		if (r <= a || b <= l) return 0;
		if (a <= l && r <= b) return v[k];
		long long lc = query(a, b, k * 2, l, (l + r) >> 1);
		long long rc = query(a, b, k * 2 + 1, (l + r) >> 1, r);
		return merge(lc, rc);
	}
 
public:
	LazySegmentTree() : v(vector<long long>()), lazy(vector<long long>()) {};
	LazySegmentTree(int n) {
		for (size_ = 1; size_ < n;) size_ <<= 1;
		v.resize(size_ * 2);
		lazy.resize(size_ * 2);
	}
	inline void push(int k, int l, int r) {
		if (lazy[k] != 0) {
			v[k] += lazy[k];
			if (r - l > 1) {
				lazy[k * 2] += lazy[k];
				lazy[k * 2 + 1] += lazy[k];
			}
			lazy[k] = 0;
		}
	}
	inline long long merge(long long x, long long y) {
		return max(x,y);
	}
	inline void update(int l, int r, long long x) {
		update(l, r, x, 1, 0, size_);
	}
	inline long long query(int l, int r) {
		return query(l, r, 1, 0, size_);
	}
};

ll active[222222];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n; cin>>n;
	for(ll i=0;i<n;i++)
	{
		cin>>a[i];
		a[i]=n-a[i]-1;
		if(a[i]>=0) Y[a[i]].pb(i);
	}
	ll q; cin>>q;
	ll ans = 0;
	for(ll i=0;i<q;i++)
	{
		ll x,y; cin>>x>>y; x--;  
		ll v;cin>>v;
		ptx[x].pb({n-y,v});
		ans+=v;
	}
	for(ll i=0;i<n;i++)
	{
		sort(ptx[i].rbegin(),ptx[i].rend());
		vector<ii> S;
		for(ii z:ptx[i])
		{
			if(!S.empty()&&z.se<=S.back().se) continue;
			S.pb(z);
		}
		ll las=0;
		for(ii x:S)
		{
			pty[x.fi].pb({i,x.se-las});
			las=x.se;
		}
	}
	DSU dsu(n);
	LazySegmentTree st(n);
	for(ll i=n-1;i>=0;i--)
	{
		//merge
		for(ll x:Y[i])
		{
			ll ans=0;
			ll resl=0;
			ll resr=0;
			if(x-1>=0&&active[x-1])
			{
				ll rt = dsu.rt(x-1);
				ll l = dsu.dsu[rt].l; ll r = dsu.dsu[rt].r;
				resl=st.query(l,r+1);
				ans+=resl;
			}
			if(x+1<n&&active[x+1])
			{
				ll rt = dsu.rt(x+1);
				ll l = dsu.dsu[rt].l; ll r = dsu.dsu[rt].r;
				resr=st.query(l,r+1);
				ans+=resr;
			}
			if(x-1>=0&&active[x-1])
			{
				ll rt = dsu.rt(x-1);
				ll l = dsu.dsu[rt].l; ll r = dsu.dsu[rt].r;
				st.update(l,r+1,resr);
			}
			if(x+1<n&&active[x+1])
			{
				ll rt = dsu.rt(x+1);
				ll l = dsu.dsu[rt].l; ll r = dsu.dsu[rt].r;
				st.update(l,r+1,resl);
			}
			if(x-1>=0&&active[x-1]) dsu.merge(x-1,x);
			if(x+1<n&&active[x+1]) dsu.merge(x,x+1);
			active[x]=1;
			st.update(x,x+1,ans);
		}
		//extend
		for(ii pt:pty[i])
		{
			ll x=pt.fi; ll v = pt.se;
			st.update(x,x+1,v);
		}
	}
	ll mx=0; ll sum=0;
	for(ll i=0;i<n;i++)
	{
		if(a[i]<0)
		{
			sum+=mx;
			mx=0; continue;
		}
		mx=max(mx,st.query(i,i+1));
	}
	sum+=mx;
	ans-=sum;
	cout<<ans<<'\n';
}

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