Submission #1369499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1369499		dragonlyz123	Gift Boxes (EGOI25_giftboxes)	C++20	100 / 100	146 ms	54460 KiB

Main

/*
─────────────────────────────────────────────────────────────────────────────────────
 ██╗     ███████╗███████╗    ██╗   ██╗███████╗███╗   ██╗    ███████╗███████╗███████╗
 ██║     ██╔════╝██╔════╝    ╚██╗ ██╔╝██╔══██╗████╗  ██║    ╚══███╔╝██╔════╝██╔════╝
 ██║     █████╗  █████╗       ╚████╔╝ ███████║██╔██╗ ██║      ███╔╝ █████╗  █████╗
 ██║     ██╔══╝  ██╔══╝        ╚██╔╝  ██╔══██║██║╚██╗██║     ███╔╝  ██╔══╝  ██╔══╝
 ███████╗███████╗███████╗       ██║   ██║  ██║██║ ╚████║    ███████╗███████╗███████╗
 ╚══════╝╚══════╝╚══════╝       ╚═╝   ╚═╝  ╚═╝╚═╝  ╚═══╝    ╚══════╝╚══════╝╚══════╝
 ─────────────────────────────────────────────────────────────────────────────────────
							» Stay hungry, stay foolish. «
*/
 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ld = long double;
 
ll ll_max = 2e18;
ll ll_min = -2e18;
 
void set_io(string name = "") {
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	if (!name.empty()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

void solve() {
	ll t, n; cin >> t >> n;
	vector<ll> a(n);
	vector<pair<ll, ll>> b(t);
	for (ll i = 0; i < t; i++) {
		b[i].first = ll_max;
		b[i].second = ll_min;
	}
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
		b[a[i]].first = min(b[a[i]].first, i);
		b[a[i]].second = max(b[a[i]].second, i);
	}
	ll l = -1, r = -1;
	unordered_set<ll> y, z;
	for (ll i = 0; i < n; i++) {
		// for (ll abc : y) cout << abc << " ";
		// cout << "\n";
		if (y.find(a[i]) == y.end()) {
			// cout << a[i] << "\n";
			r = i;
			y.emplace(a[i]);
		} else {
			break;
		}
	}
	for (ll i = n - 1; i >= 0; i--) {
		if (z.find(a[i]) == z.end()) {
			l = i;
			z.emplace(a[i]);
		} else {
			break;
		}
	}
	ll o = ll_min, p = ll_max;
	ll c = 0, d = 0;
	// cout << "r" << " " << r << "\n";
	for (ll i = 0; i <= r; i++) {
		c = max(c, b[a[i]].second);
		ll u = i + 1, v = max(c + 1, l) - 1;
		// cout << u << " " << v << "\n";
		if (u <= v && v - u <= p - o) {
			o = u;
			p = v;
		}
	}
	// cout << "l" << " " << l << "\n";
	for (ll i = n - 1; i >= l; i--) {
		d = min(d, b[a[i]].first);
		ll u = min(d - 1, r) + 1, v = i - 1;
		// cout << u << " " << v << "\n";
		if (u <= v && v - u <= p - o) {
			o = u;
			p = v;
		}
	}
	// cout << "rl\n";
	cout << o << " " << p << "\n";
}

int main() {
    set_io();
    // ll t; cin >> t;
    // while (t--) {
    //     solve();
    // }
    solve();
    return 0;
}

// g++-15 -std=c++23 -O2 solution.cpp -o solution
// ./solution

Compilation message (stderr)

Main.cpp: In function 'void set_io(std::string)':
Main.cpp:26:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |                 freopen((name + ".in").c_str(), "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:27:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |                 freopen((name + ".out").c_str(), "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 24 / 24