Submission #884082

#	Time	Username	Problem	Language	Result	Execution time	Memory
884082		salyg1n	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	264 ms	23888 KiB

Main

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define mp make_pair
#define uset unordered_set
#define umap unordered_map
#define mset multiset
#define lb lower_bound
#define ub upper_bound
//#define int long long

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef set<int> si;
typedef vector<si> vsi;
typedef mset<int> msi;
typedef vector<msi> vmsi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<vpi> vvpi;
typedef set<pi> spi;
typedef mset<pi> mspi;
typedef vector<spi> vspi;
typedef tuple<int, int, int> ti;
typedef vector<ti> vti;
typedef vector<vti> vvti;
typedef set<ti> sti;
typedef mset<ti> msti;
typedef vector<sti> vsti;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef map<int, int> mii;

mt19937 rnd(228);

template<typename t> bool minravno(t& a, t b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}
template<typename t> bool maxravno(t& a, t b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}
template<typename t> void input(t& a, int i = 0, int j = -1) {
	if (j == -1)
		j = a.size() - 1;
	for (int k = i; k <= j; ++k) {
		cin >> a[k];
	}
}

const int MAXN = 2e5 + 10, MAX = 1e4 + 10, INF = 1e18, MOD = 998244353;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	vi a(n + 1);
	input(a, 1);
	spi s;
	mii m;
	s.insert({1, a[1]});
	m[a[1]] = 1;
	for (int i = 2; i <= n; ++i) {
		if (!m.count(a[i])) {
			m[a[i]] = i;
			s.insert({i, a[i]});
			continue;
		}
		int j = m[a[i]];
		while (s.ub({j, a[i]}) != s.end()) {
			auto [k, x] = *s.ub({j, a[i]});
			m.erase(x);
			s.erase({k, x});
		}
		m[a[i]] = i;
	}
	s.insert({n + 1, 0});
	while (s.size() >= 2) {
		auto [i, x] = *s.begin();
		auto [j, y] = *(++s.begin());
		for (int k = 0; k < j - i; ++k)
			cout << x << '\n';
		s.erase(s.begin());
	}


	return 0;
}

Compilation message (stderr)

Main.cpp:64:50: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   64 | const int MAXN = 2e5 + 10, MAX = 1e4 + 10, INF = 1e18, MOD = 998244353;
      |                                                  ^~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40