제출 #260541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260541		amoo_safar	별자리 3 (JOI20_constellation3)	C++17	100 / 100	1146 ms	89948 KiB

constellation3

// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

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

const int N = 2e5 + 10;
const int Log = 20;
const int Inf = 1'000'000'001;

struct Fenwick {
	ll fen[N];
	Fenwick (){
		memset(fen, 0, sizeof fen);
	}

	void Add(int idx, ll d){
		for(; idx < N; idx += (idx & (-idx)))
			fen[idx] += d;
	}
	ll Get(int idx){
		ll res = 0;
		for(; idx; idx -= (idx & (-idx)))
			res += fen[idx];
		return res;
	}
	void AddLR(int L, int R, ll d){
		Add(L, d);
		Add(R, -d);
	}
};

Fenwick fr, fl;

int n, A[N];
pii sp[Log][N];

int BigR(int idx, pii V){
	int res = idx;
	for(int l = Log - 1; l >= 0; l--)
		if(sp[l][res] <= V)
			res += 1 << l;
	return res;
}
int BigL(int idx, pii V){
	int res = idx;
	for(int l = Log - 1; l >= 0; l--)
		if(sp[l][max(0, res - (1 << l) + 1)] <= V)
			res -= 1 << l;
	return res;
}
pii Max(int L, int R){
	L ++;
	pii res = {-1, -1};
	for(int l = Log - 1; l >= 0; l--){
		if(L + (1 << l) <= R){
			res = max(res, sp[l][L]);
			L += 1 << l;
		}
	}
	return res;
}

int m;
int X[N], Y[N], C[N];

map<pii, vector<int> > mp;
map<pii, ll> dp;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> A[i];
	A[0] = A[n + 1] = Inf;
	
	for(int i = 0; i <= n + 1; i++){
		sp[0][i] = pii(A[i], i);
	}
	for(int l = 1; l < Log; l++)
		for(int i = 0; i <= n + 1; i++)
			sp[l][i] = max(sp[l - 1][i], sp[l - 1][min(n + 1, i + (1 << (l-1)) )] );

	vector<pii> seg;
	for(int i = 1; i <= n; i++){
		//cerr << BigL(i, pii(A[i], i)) << ' ' << BigR(i, pii(A[i], i)) << '\n';
		seg.pb({i, BigR(i, pii(A[i], i) )});
		seg.pb({BigL(i, pii(A[i], i) ), i});
	}
	seg.pb({0, n + 1});
	sort(all(seg)); seg.resize(unique(all(seg)) - seg.begin());
	sort(all(seg), [&](pii A, pii B){
		if(A.S - A.F == B.S - B.F) return A.F < B.F;
		return A.S - A.F < B.S - B.F;
	});


	ll Sum = 0;
	cin >> m;
	for(int i = 1; i <= m; i++){
		cin >> X[i] >> Y[i] >> C[i];
		mp[pii( BigL(X[i], pii(Y[i], -1)), BigR(X[i], pii(Y[i], -1)) )].pb(i);
		Sum += C[i];
	}
	//debug("Start");
	ll res;
	
	for(auto [L, R] : seg){
		if(R - L == 1) continue;
		int mx = Max(L, R).S;		
		res = dp[{L, mx}] + dp[{mx, R}];

		vector<int> &V = mp[{L, R}];
		for(auto st : V){
			/*debug(st);
			if(st == 4){
			cerr << fr.Get(X[st]) << " " << fr.Get(R) << '\n';
			cerr << "! " << st << " : " << (fr.Get(X[st]) - fr.Get(R)) << ", " << (fl.Get(X[st]) - fl.Get(L)) << '\n';
			}*/

			res = max(res, C[st] + (fr.Get(X[st]) - fr.Get(R)) + (fl.Get(X[st]) - fl.Get(L)) ) ;
		}
		dp[{L, R}] = res;

		//cerr << L << "->" << R << " : " << res << '\n';
		if(pii(L, R) == pii(0, n + 1)) continue;

		if(pii(A[L], L) < pii(A[R], R) ){
			//cerr << "# " << L  << ' ' << R << ' ' << res << '\n';
			fr.AddLR(BigL(L, pii(A[L], L)) + 1, L + 1, res);
		} else {
			fl.AddLR(R, BigR(R, pii(A[R], R)), res);
		}
	}
	cout << Sum - dp[{0, n + 1}] << '\n';
	return 0;
}

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