Submission #1273471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273471		mat_jur	Group Photo (JOI21_ho_t3)	C++20	100 / 100	1645 ms	624 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

const int inf = 1e9+10;

struct segtree {
	int base;
	vector<int> t;
	segtree(int n) {
		base = 1;
		while (base < n) base *= 2;
		t.resize(2*base);
	}

	void update(int v, int x) {
		v += base;
		while (v)
			t[v] += x, v /= 2;
	}

	int query(int l, int r) {
		l += base - 1; r += base + 1;
		int res = 0;
		while (l/2 != r/2) {
			if (l%2 == 0) res += t[l+1];
			if (r%2 == 1) res += t[r-1];
			l /= 2; r /= 2;
		}
		return res;
	}
};	

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n;
	cin >> n;
	vector<int> h(n);
	for (int &x : h) {
		cin >> x;
		--x;
	}

	vector<int> p(n);
	for (int i = 0; i < n; ++i) p[h[i]] = i;

	vector<int> dp(n+1, inf);
	dp[n] = 0;
	segtree l(n);
	for (int j = n-1; j >= 0; --j) {
		l.update(p[j], 1);
		int pref = 0;
		segtree r(n);
		for (int i = j; i < n; ++i) {
			int pos = p[i];	
			pref += l.query(0, pos-1) - r.query(pos, n-1);
			r.update(pos, +1);
			dp[j] = min(dp[j], pref + dp[i+1]);
		}
	}

	cout << dp[0] << '\n';
	
	return 0;
}

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