Submission #1125665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125665		Kel_Mahmut	Group Photo (JOI21_ho_t3)	C++20	100 / 100	4599 ms	196652 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

struct SegmentTree{
	int n;
	vector<int> t;
	SegmentTree(int n) : n(n), t(4 * n){}
	void upd(int u, int tl, int tr, int pos, int val){
		if(tl == tr){
			t[u] = val;
			return;
		}
		int tm = (tl + tr) / 2;
		if(pos <= tm)
			upd(u * 2, tl, tm, pos, val);
		else
			upd(u * 2 + 1, tm + 1, tr, pos, val);
		t[u] = t[u * 2] + t[u * 2 + 1];
	}

	void upd(int pos, int val){
		upd(1, 0, n - 1, pos, val);
	}

	int query(int u, int tl, int tr, int ql, int qr){
		if(ql <= tl && tr <= qr){
			return t[u];
		}
		int tm = (tl + tr) / 2;
		int ret = 0;
		if(ql <= tm)
			ret += query(u * 2, tl, tm, ql, qr);
		if(tm < qr)
			ret += query(u * 2 + 1, tm + 1, tr, ql, qr);
		return ret;
	}

	int query(int ql, int qr){
		return query(1, 0, n - 1, ql, qr);
	}
};

int main(){
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++) cin >> a[i], a[i]--;
	vector<int> pos(n);
	for(int i = 0; i < n; i++) pos[a[i]] = i;
	vector<vector<int>> inv(n, vector<int>(n));
	for(int r = n - 1; r >= 0; r--){
		SegmentTree st(n);
		int cur = 0;
		for(int l = r; l >= 0; l--){
			cur += st.query(pos[l], n - 1);
			inv[l][r] = cur;
			st.upd(pos[l], 1);
		}
	}

	vector<vector<int>> cros(n + 1, vector<int>(n + 1));
	for(int l = 0; l <= n; l++){
		SegmentTree st(n);
		for(int i = 1; i <= l; i++){
			st.upd(pos[i - 1], 1);
		}
		int cur = 0;
		for(int r = l + 1; r <= n; r++){
			cur += st.query(pos[r - 1], n - 1);
			cros[l][r] = cur;
		}
	}

	vector<int> dp(n + 1);
	for(int k = 1; k <= n; k++){
		dp[k] = INT_MAX;
		for(int j = 0; j < k; j++){
			dp[k] = min(dp[k], dp[j] + inv[j][k - 1] + cros[j][k]);
		}
	}
	cout << dp[n] << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36