Submission #899607

#	Time	Username	Problem	Language	Result	Execution time	Memory
899607		simona1230	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	220 ms	29668 KiB

Main

#include <bits/stdc++.h>

using namespace std;
int n;
map<int,vector<int> > mp;
int t[800001];

int query(int i,int l,int r,int idx)
{
    if(l==r||t[i])return t[i];
    int m=(l+r)/2;
    if(idx<=m)return query(i*2,l,m,idx);
    else return query(i*2+1,m+1,r,idx);
}

void update(int i,int l,int r,int ql,int qr)
{
    if(ql>qr||t[i])return;
    if(ql<=l&&r<=qr)
    {
        t[i]=1;
        return;
    }
    int m=(l+r)/2;
    update(i*2,l,m,ql,min(m,qr));
    update(i*2+1,m+1,r,max(m+1,ql),qr);
}

int l[200001],val[200001];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        val[i]=x;
        while(mp[x].size()&&query(1,1,n,mp[x][mp[x].size()-1])==1)
            mp[x].pop_back();

        if(mp[x].size())
        {
            l[i]=mp[x][mp[x].size()-1];
            update(1,1,n,mp[x][mp[x].size()-1],i-1);
        }
        else l[i]=i;
        mp[x].push_back(i);
    }
}

void print()
{
    int curr=n;
    vector<int> ans;
    for(int i=n;i>=1;i--)
    {
        while(curr>=l[i])
        {
            ans.push_back(val[i]);
            curr--;
        }
    }
    for(int i=n-1;i>=0;i--)
        cout<<ans[i]<<" ";
    cout<<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solve();
	print();
	return 0;
}

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