Submission #838097

#	Time	Username	Problem	Language	Result	Execution time	Memory
838097		MohamedAhmed04	Constellation 3 (JOI20_constellation3)	C++14	0 / 100	2 ms	4948 KiB

constellation3

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;

int arr[MAX] ;
int n , m ;

vector< pair<int , int> >vp[MAX] ;

long long maxdp[MAX] ;
long long Max = 0 ;

int L[MAX] , R[MAX] ;

void solve(int l , int r)
{
	if(l > r)
		return ;
	int idx = -1 ;
	for(int i = l , j = r ; i <= j ; ++i , --j)
	{
		if(L[i] <= l && R[i] >= r)
		{
			idx = i ;
			break ;
		}
		if(L[j] <= l && R[j] >= r)
		{
			idx = j ;
			break ;
		}
	}
	assert(idx != -1) ;
	long long curMax = 0 ; 
	for(int i = 1 ; i <= n ; ++i)
	{
		if(i >= l && i <= r)
			continue ;
		curMax = max(curMax , maxdp[i]) ;
	}
	for(int i = l ; i <= r ; ++i)
	{
		while(vp[i].size() && vp[i].back().first <= arr[idx])
		{
			pair<int , int>p = vp[i].back() ;
			vp[i].pop_back() ;
			maxdp[i] = max(maxdp[i] , curMax + p.second) ;
			Max = max(Max , maxdp[i]) ;
		}
	}
	solve(l , idx-1) , solve(idx+1 , r) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] , arr[i] = n-arr[i] ;
	cin>>m ;
	long long ans = 0 ;
	for(int i = 0 ; i < m ; ++i)
	{
		int i2 , j2 , x ;
		cin>>i2>>j2>>x ;
		vp[i2].emplace_back(n-j2+1 , x) ;
		ans += x ;
	}
	for(int i = 1 ; i <= n ; ++i)
		sort(vp[i].begin() , vp[i].end()) , reverse(vp[i].begin() , vp[i].end()) ;
	stack<int>s ;
	for(int i = 1 ; i <= n ; ++i)
	{
		L[i] = 1 ;
		while(s.size() && arr[i] < arr[s.top()])
			s.pop() ;
		if(s.size())
			L[i] = s.top() + 1 ;
		s.push(i) ;
	}
	while(s.size())
		s.pop() ;
	for(int i = n ; i >= 1 ; --i)
	{
		R[i] = n ;
		while(s.size() && arr[i] <= arr[s.top()])
			s.pop() ;
		if(s.size())
			R[i] = s.top() - 1 ;
		s.push(i) ;
	}
	solve(1 , n) ;
	ans -= Max ;
	return cout<<ans<<"\n" , 0 ;
}		

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