Submission #1271188

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

Main

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int MAXN = 1e5 + 5;

map<int, pii> segment;
unordered_map<int, set<int>> color;
int n;
int a[MAXN];
int ans[MAXN];

int 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++)
    {
        int 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--;
                int laststart = *it;
                int lastend = segment[laststart].first;
                int j = lastend;
                if (j == i - 1)
                {
                    segment[laststart] = {i, col};
                }
                else
                {
                    auto pos = segment.lower_bound(j + 1);
                    vector<int> del;
                    while(pos != segment.end() and pos->first <= i - 1)
                    {
                        del.push_back(pos->first);
                        pos++;
                    }
                    for (int start : del)
                    {
                        int 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)
    {
        int s = cak.first;
        int e = cak.second.first;
        int c = cak.second.second;
        for (int 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