Submission #1179844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179844		Szymon_Pilipczuk	Stone Arranging 2 (JOI23_ho_t1)	C++20	100 / 100	111 ms	13964 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
int cu = 1;
pair<int,int> tr[400000];
    int n;

void add(int l,int r,int v)
{
    l+=n;
    r+=n;
    tr[l] = {v,cu};
    tr[r] = {v,cu};
    while(l/2 != r/2)
    {
        if(l%2==0)tr[l+1]={v,cu};
        if(r%2 == 1) tr[r-1] = {v,cu};
        l/=2;r/=2;
    }
    cu++;
}
int check(int p)
{
    p+=n;
    int c = -1;
    int ans;
    while(p > 0)
    {
        if(tr[p].nd > c)
        {
            ans = tr[p].st;
            c = tr[p].nd;
        }
        p/=2;
    }
    return ans;
}
int main()
{
    cin>>n;
    int a[n];
    unordered_map<int,pair<int,int>> m;
    for(int i =0 ;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i = 0;i<n;i++)
    {
        if(m[a[i]].st != 0)
        {
            int j = m[a[i]].nd+1;
            while(j < i+1)
            {
                int c = check(j-1);
                //cout<<c<<"\n";
                j = m[c].nd+1;
                m[c] = {0,0};
            }
            add(m[a[i]].nd,i,a[i]);
            m[a[i]].nd = i+1;
        }
        else
        {
            m[a[i]] = {i+1,i+1};
            add(i,i,a[i]);
        }
    }
    for(int i =0 ;i<n;i++)
    {
        cout<<check(i)<<"\n";
    }
}

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