Submission #831718

#	Time	Username	Problem	Language	Result	Execution time	Memory
831718		green_gold_dog	Group Photo (JOI21_ho_t3)	C++17	64 / 100	5002 ms	321224 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef int ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9000000000000000000, INF32 = 2000000000, MOD = 1000000007;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
bool assign_min(T& a, T b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
T square(T a) {
	return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
	ll operator() (pair<ll, ll> p) {
		return ((__int128)p.first * MOD + p.second) % INF64;
	}
};

struct segment_tree {
	vector<ll> tree;
	ll size;
	segment_tree(vector<ll> a = vector<ll>(0, 0)) {
		size = 1;
		while (size < a.size()) {
			size *= 2;
		}
		tree.resize(size * 2, 0);
		a.resize(size, 0);
		build(1, 0, size, a);
	}
	ll build(ll v, ll l, ll r, vector<ll>& a) {
		if (r - l == 1) {
			return tree[v] = a[l];
		}
		ll mid = (l + r) / 2;
		return tree[v] = build(v * 2, l, mid, a) + build(v * 2 + 1, mid, r, a);
	}
	ll get(ll l, ll r) {
		return get(1, 0, size, l, r);
	}
	ll get(ll v, ll l, ll r, ll ql, ll qr) {
		if (ql <= l && r <= qr) {
			return tree[v];
		}
		if (qr <= l || r <= ql) {
			return 0;
		}
		ll mid = (l + r) / 2;
		return get(v * 2, l, mid, ql, qr) + get(v * 2 + 1, mid, r, ql, qr);
	}
};

void solve() {
	ll n;
	cin >> n;
	vector<ll> pos(n);
	for (ll i = 0; i < n; i++) {
		ll x;
		cin >> x;
		x--;
		pos[x] = i;
	}
	vector<segment_tree> all;
	for (ll i = 0; i <= n; i++) {
		vector<ll> now(n);
		for (ll j = 0; j < n; j++) {
			now[j] = pos[j] > i;
		}
		all.emplace_back(now);
	}
	vector<ll> dp(n, INF32);
	dp[0] = 0;
	for (ll i = 1; i < n; i++) {
		ll now = 0;
		for (ll j = i - 1; j >= 0; j--) {
			now += all[pos[j + 1]].get(0, j + 1);
			//for (ll k = 0; k <= j; k++) {
			//	if (pos[k] > pos[j + 1]) {
			//		now++;
			//	}
			//}
			ll x = all[pos[j + 1]].get(j + 2, i + 1);
			now += x;
			now -= (i - j - 1) - x;
			//for (ll k = j + 2; k <= i; k++) {
			//	if (pos[k] > pos[j + 1]) {
			//		now++;
			//	} else {
			//		now--;
			//	}
			//}
			assign_min(dp[i], now + dp[j]);
		}
		now = 0;
		for (ll k = 0; k <= i; k++) {
			now += k - all[pos[k]].get(0, k);
			//for (ll l = 0; l < k; l++) {
			//	if (pos[k] > pos[l]) {
			//		now++;
			//	}
			//}
		}
		assign_min(dp[i], now);
	}
	cout << dp.back() << '\n';
}

int main() {
	if (IS_FILE) {
		freopen("", "r", stdin);
		freopen("", "w", stdout);
	}
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
	ll t = 1;
	if (IS_TEST_CASES) {
		cin >> t;
	}
	for (ll i = 0; i < t; i++) {
		solve();
	}
}

Compilation message (stderr)

Main.cpp:12:22: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '9000000000000000000' to '-494665728' [-Woverflow]
   12 | constexpr ll INF64 = 9000000000000000000, INF32 = 2000000000, MOD = 1000000007;
      |                      ^~~~~~~~~~~~~~~~~~~
Main.cpp: In constructor 'segment_tree::segment_tree(std::vector<int>)':
Main.cpp:55:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   while (size < a.size()) {
      |          ~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:141:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |   freopen("", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:142:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |   freopen("", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~

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