Submission #221461

#	Time	Username	Problem	Language	Result	Execution time	Memory
221461		patrikpavic2	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	1158 ms	126376 KiB

constellation3

#include <cstdio>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef pair < int, int > pii;
typedef vector < int > vi;
typedef long long ll;

const int N = 2e5 + 500;
const int LOG = 18;

map < int, ll > dp[N];
map < int, vi > sjec[N];

int n, m, kol[N];
int A[N], zvj[N], C[N];
int L[N], R[N], pos[N];
int rmq[N][LOG];
int par[N][2];
vector < pii > bitni;
vi T[N][2];
int Q_L[N][2], Q_R[N][2], cur = 0;
ll loga[N][2];

bool cmp(const pii &A,const pii &B){
	return A.Y - A.X < B.Y - B.X;
}

void dfs(int x,int fl){
	Q_L[x][fl] = cur++;
	for(int y : T[x][fl])
		dfs(y, fl);
	Q_R[x][fl] = cur;
}

void add(int x,int fl, ll y){
	for(x += 10; x < N ; x += x & -x)
		loga[x][fl] += y;
}

ll get(int x, int fl){
	ll ret = 0;
	for(x += 10; x ; x -= x & -x)
		ret += loga[x][fl];
	return ret;
}

inline int maax(int i,int j){
	if(A[i] > A[j]) 
		return i;
	return j;
}

inline int get_maax(int l,int r){
	return maax(rmq[l][kol[r - l + 1]], rmq[r - (1 << kol[r - l + 1]) + 1][kol[r - l + 1]]);
}

ll svi_C = 0;

ll f(int l,int r){
	if(r < l) return 0;
	if(dp[l][r] != 0) return dp[l][r] - 1;
	int mks = get_maax(l, r);
	ll ret = f(l, mks - 1) + f(mks + 1, r);
	for(int x : sjec[l][r])
		ret = max(ret, f(l,  pos[x] - 1) + f(pos[x] + 1, r) + C[x]);
	dp[l][r] = ret + 1;
	return ret;
}



int main(){
	scanf("%d", &n);
	vector < pii > saz;
	for(int i = 1;i <= n;i++){
		scanf("%d", A + i);
		rmq[i][0] = i;
	
	}
	scanf("%d", &m);
	for(int i = 1;i <= n;i++)
		saz.PB({A[i], i + m});
	for(int i = 0;i < m;i++){
		scanf("%d%d%d", pos + i, zvj + i, C + i); 
		saz.PB({zvj[i], i});
	}
	sort(saz.begin(), saz.end());
	for(int i = 0;i < n + m;i++){
		if(saz[i].Y < m)
			zvj[saz[i].Y] = i + 1;
		else
			A[saz[i].Y - m] = i + 1;
	}
	A[0] = n + m  + 1, A[n + 1] = n + m + 1;
	stack < int > s; s.push(0);
	for(int i = 1;i <= n;i++){
		for(;A[s.top()] < A[i];s.pop());
		par[i][0] = s.top(); s.push(i);
		if(par[i][0] < i - 1)
			bitni.PB({par[i][0] , i});
		T[par[i][0]][0].PB(i);
	}
	bitni.PB({0, n + 1});
	for(;!s.empty();s.pop());
	s.push(n + 1);
	for(int i = n;i >= 1;i--){
		for(;A[s.top()] < A[i];s.pop());
		par[i][1] = s.top(); s.push(i);
		if(par[i][1] > i + 1)
			bitni.PB({i , par[i][1]});
		T[par[i][1]][1].PB(i);
	}
	dfs(0, 0); cur = 0; dfs(n + 1, 1);
	for(int i = 1;i <= n + 2;i++){
		{for(;(1 << kol[i]) <= i;kol[i]++); kol[i]--;}
		rmq[i][0] = i;
	}
	for(int j = 1;j < LOG;j++){
		for(int i = 0;i <= n + 1;i++){
			rmq[i][j] = rmq[i][j - 1];
			if(i + (1 << (j - 1)) <= n + 1)
				rmq[i][j] = maax(rmq[i][j], rmq[i + (1 << (j - 1))][j - 1]);
		}
	}
	for(int i = 0;i < m;i++){
		L[i] = pos[i], R[i] = pos[i];
		for(int j = LOG - 1;j >= 0;j--){
			if(L[i] - (1 << j) >= 1 && A[get_maax(L[i] - (1 << j), pos[i])] < zvj[i]) 
				L[i] -= (1 << j);
			if(R[i] + (1 << j) <= n &&  A[get_maax(pos[i], R[i] + (1 << j))] < zvj[i])  
				R[i] += (1 << j);
		}
		L[i]--, R[i]++;
		sjec[L[i]][R[i]].PB(i); svi_C += C[i];
	}
	sort(bitni.begin(), bitni.end(), cmp);
	for(pii ja : bitni){
		int l = ja.X, r = ja.Y;
		int mks = get_maax(l + 1, r - 1);
		ll cur = dp[l][mks] + dp[mks][r];
		for(int x : sjec[l][r]){
			cur = max(cur, (ll)C[x] + get(Q_L[pos[x]][0], 0) + get(Q_L[pos[x]][1], 1) - get(Q_L[l][0], 0) - get(Q_L[r][1], 1));
		}
		dp[l][r] = cur;
		if(A[l] > A[r]){
			add(Q_L[r][0], 0, cur);
			add(Q_R[r][0], 0, -cur);
		}
		if(A[l] < A[r]){
			add(Q_L[l][1], 1, cur);
			add(Q_R[l][1], 1, -cur);
		}
	}	
	printf("%lld\n", svi_C - dp[0][n + 1]);
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
constellation3.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A + i);
   ~~~~~^~~~~~~~~~~~~
constellation3.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
constellation3.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", pos + i, zvj + i, C + i); 
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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