Submission #1271192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271192		hoangtien69	Stone Arranging 2 (JOI23_ho_t1)	C++20	25 / 100	4 ms	1096 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, ll>
const int MAXN = 1e5 + 5;
#define ll long long
map<ll, pii> segment;
unordered_map<ll, set<int>> color;
ll n;
ll a[MAXN];
ll ans[MAXN];

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

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        ll col = a[i];
        if (i == 1)
        {
            segment[1] = {1, col};
            color[col].insert(1);
        }
        else
        {
            if (color[col].empty())
            {
                segment[i] = {i, col};
                color[col].insert(i);
            }
            else
            {
                auto it = color[col].end();
                it--;
                ll laststart = *it;
                ll lastend = segment[laststart].first;
                ll j = lastend;
                if (j == i - 1)
                {
                    segment[laststart] = {i, col};
                }
                else
                {
                    auto pos = segment.lower_bound(j + 1);
                    vector<ll> del;
                    while(pos != segment.end() and pos->first <= i - 1)
                    {
                        del.push_back(pos->first);
                        pos++;
                    }
                    for (ll start : del)
                    {
                        ll c2 = segment[start].second;
                        segment.erase(start);
                        color[c2].erase(start);
                    }
                    segment[j + 1] = {i, col};
                    color[col].insert(j + 1);
                }
            }
        }
    }
    for (auto cak : segment)
    {
        ll s = cak.first;
        ll e = cak.second.first;
        ll c = cak.second.second;
        for (ll k = s; k <= e; k++)
        {
            ans[k] = c;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << "\n";
    }
}

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