Submission #262337

#	Time	Username	Problem	Language	Result	Execution time	Memory
262337		easrui	Constellation 3 (JOI20_constellation3)	C++14	35 / 100	357 ms	33872 KiB

constellation3

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

const int MN = 2e5+5;

int N,A[MN],X[MN],Y[MN],C[MN],T[MN<<1];
ll L[MN],R[MN];
vector<int> V[MN];

void upt(int s, int e, int x, int v, int i)
{
	int m = (s+e)/2;
	if(s==e){
		T[i] = v;
		return;
	}
	if(x<=m) upt(s,m,x,v,i<<1);
	else upt(m+1,e,x,v,i<<1|1);
	T[i] = A[T[i<<1]]>A[T[i<<1|1]] ? T[i<<1] : T[i<<1|1];
}

int getm(int s, int e, int x, int y, int i)
{
	if(e<x||y<s) return 0;
	if(x<=s&&e<=y) return T[i];
	int m = (s+e)/2;
	int l = getm(s,m,x,y,i<<1), r = getm(m+1,e,x,y,i<<1|1);
	return A[l]>A[r] ? l : r;
}

int maxc(int x, int y)
{
	int res = 0;
	for(int i:V[x]){
		if(Y[i]>y) continue;
		res = max(res,C[i]);
	}
	return res;
}

ll solve(int s, int e, int y)
{
	if(s<1||e>N||s>e) return 0;
	//cout << s << ' ' << e << ' ' << y << '\n';
	int m = getm(1,N,s,e,1);
	if(L[m]<0) L[m] = solve(s,m-1,A[m]);
	if(R[m]<0) R[m] = solve(m+1,e,A[m]);

	ll res = L[m]+R[m]+maxc(m,y);
	res = max(res,solve(s,m-1,y)+R[m]);
	res = max(res,L[m]+solve(m+1,e,y));
	return res;
}

int main()
{
	/*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif*/
	
    ios_base::sync_with_stdio(0),cin.tie(0);

    cin >> N;
    for(int i=1; i<=N; i++){
    	cin >> A[i];
    	upt(1,N,i,i,1);
    	L[i] = R[i] = -1;
    }
    A[0] = -1;

    int M;
    cin >> M;
    ll sum = 0;
    for(int i=0; i<M; i++){
    	cin >> X[i] >> Y[i] >> C[i];
    	V[X[i]].push_back(i);
    	sum += C[i];
    }
    cout << sum-solve(1,N,N);
}

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