Submission #1043999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043999		12345678	Editor (BOI15_edi)	C++17	0 / 100	1 ms	860 KiB

edi

#include <bits/stdc++.h>

using namespace std;

const int nx=5e3+5;

int n, a, t[nx], vl[nx], p[nx], sz[nx], c[nx], cnt[nx];
vector<int> d[nx], g[nx];
set<int> s;

void dfs(int u, int rt)
{
    c[u]=rt;
    for (auto v:g[u]) dfs(v, rt);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) 
    {
        cin>>t[i];
        sz[i]=1;
        if (t[i]<0) t[i]=-t[i], d[t[i]].push_back(i);
        else vl[i]=t[i], t[i]=0;
    }
    for (int i=n; i>=1; i--)
    {
        for (auto x:d[i])
        {
            int y=x;
            while (t[y]>=t[x]||((sz[y]%2)==0)) y--;
            sz[y]+=sz[x];
            g[y].push_back(x);
        }
    }
    s.insert(0);
    for (int i=1; i<=n; i++) if (!t[i]) dfs(i, i);
    //for (int i=1; i<=n; i++) cout<<"c "<<i<<' '<<c[i]<<'\n';
    for (int i=1; i<=n; i++)
    {
        cnt[c[i]]++;
        if ((cnt[c[i]]%2)==1) s.insert(c[i]);
        else s.erase(c[i]);
        cout<<vl[*prev(s.end())]<<'\n';
    }
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 15
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37