Submission #1286811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286811		WH8	Stone Arranging 2 (JOI23_ho_t1)	C++20	100 / 100	245 ms	21156 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())

signed main(){
	int n;cin>>n;
	map<int,int> m;
	vector<tuple<int,int,int>> st;
	int a[n];for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++){
		if(m[a[i]] > 0){
			int sm=0;
			while(!st.empty() and get<2>(st.back()) != a[i]){
				auto [l, r, cl] = st.back();
				st.pop_back();
				m[cl]-=r-l+1;
			}
			auto [l, r, cl]=st.back();
			sm+=i-r;
			st.pop_back();
			assert(cl==a[i]);
			m[a[i]]+=sm;
			st.push_back({l, i, a[i]});
		}
		else {
			st.push_back({i,i,a[i]});
			m[a[i]]+=1;
		}
		//~ for(auto [l, r, cl] : st){
			//~ printf("( %lld, %lld, %lld : occ of cl is %lld) ",l,r,cl, m[cl]);
		//~ }
		//~ cout<<endl;
	}
	for(auto [l, r, cl] : st){
		for(int i=l;i<=r;i++){
			cout<<cl<<"\n";
		}
	}
}

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