Submission #988176

#	Time	Username	Problem	Language	Result	Execution time	Memory
988176		dubabuba	Stone Arranging 2 (JOI23_ho_t1)	C++14	100 / 100	347 ms	20052 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int LOG = 22;
const int mxn = 1e6 + 3;
const int mod = 1e9 + 7;
map<int, int> mp;
int a[mxn], n;
int b[mxn];

void solve() {
	cin >> n;
	vector<pair<pii, int>> v;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		auto it = mp.find(a[i]);
		// cout << a[i] << endl;
		if(it != mp.end()) {
			// cout << (*it).ss << ' ' << i << endl;
			v.push_back(MP(MP((*it).ss, i), a[i]));
		}
		mp[a[i]] = i;
	}

	sort(v.begin(), v.end());
	int en = 0;
	for(pair<pii, int> p : v) {
		int l = p.ff.ff;
		int r = p.ff.ss;
		int col = p.ss;
		// cout << l << ' ' << r << ": " << col << endl;

		if(l < en) continue;
		for(int i = l; i <= r; i++)
			b[i] = col;
		en = r;
	}

	for(int i = 1; i <= n; i++)
		if(b[i] == 0) cout << a[i] << endl;
		else cout << b[i] << endl;
}

signed main() {
	#ifdef LOCAL
		auto start = chrono::high_resolution_clock::now();
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	signed t = 1;// cin >> t;
	while(t--) solve();
	
	#ifdef LOCAL
		auto end = chrono::high_resolution_clock::now();
		cout << "\n"; for(int i = 0; i <= 20; ++i) cout << '-';
		cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
	#endif
	return 0;
}

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