Submission #774778

#	Time	Username	Problem	Language	Result	Execution time	Memory
774778		vjudge1	Stone Arranging 2 (JOI23_ho_t1)	C++14	100 / 100	303 ms	42928 KiB

Main

#include <bits/stdc++.h>
#define ii pair<int,int>
#define f first
#define s second
#define pb push_back
#define int long long
#define endl '\n'
using namespace std;
const int MAXN = 1e18;
int mod = 1e9 + 7;
int a[200005];
vector<int> w[200005];
map<int,vector<int> >mp;
set<ii> s; 
void AcSolution()
{
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
	}
	for(int i = 1;i <= n;i++)
	{
		if(mp[a[i]].size() == 0)
		{
			s.insert(ii(i,a[i]));
			mp[a[i]].push_back(i);
		}
		else
		{
			int j = mp[a[i]].back();
			while(!s.empty())
			{
				auto it = s.end();
				it--;
				ii k = *it;
				if(k.first > j)
				{
					s.erase(it);
					mp[k.second].pop_back();
				}
				else
				{
					break;
				}
			}
			s.insert(ii(i,a[i]));
			mp[a[i]].push_back(i);
		}
	}
	int i = 1;
	int q = 0;
	for(auto e:s)
	{
		while(i < e.first)
		{
			cout << q << endl;
			i++;
		}
		q = e.second;
		cout << q << endl;
		i++;	
	}
}
signed main()
{
//	freopen("BDIGIT.inp", "r",stdin);
//    freopen("BDIGIT.out", "w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--)
	{
	 	AcSolution();
	}
}

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