Submission #726929

#	Time	Username	Problem	Language	Result	Execution time	Memory
726929		pls33	Editor (BOI15_edi)	C++17	15 / 100	1140 ms	15376 KiB

edi

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
template <typename F>
void _debug(F f)
{
    f();
}

#ifndef _AAAAAAAAA
#define debug(x)
#else
#define debug(x) _debug(x)
#endif
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("editor.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int n;
    cin >> n;

    vi32 command(n);
    for (auto &i : command)
    {
        cin >> i;
    }

    vi32 level = command;
    for (auto &i : level)
    {
        i = max(0, -i);
    }

    // kur ijungus patenki ir kur isjungus
    vp32 node = {{0, 0}};
    vi32 state = {0};
    set<int> active;
    active.insert(0);

    for (int i = 1; i <= n; i++)
    {
        int real = i - 1;
        if (level[real] == 0)
        {
            node.emplace_back(i, *active.rbegin());
            active.insert(i);
            state.push_back(command[real]);

            continue;
        }

        auto it = active.rbegin();
        for (; it != active.rend(); it++)
        {
            if ((*it > 0 ? level[*it - 1] : INT_MAX) < level[real])
            {
                break;
            }
        }

        if (it == active.rend() || *it == 0)
        {
            node.emplace_back(*active.rbegin(), *active.rbegin());
            active.insert(i);
            state.push_back(state[node.back().first]);
            continue;
        }

        int id = node[*it].second;

        for (; id > 0 && level[id - 1] >= 0; id = node[id].first)
        {
            active.insert(id);
            if (!level[id - 1])
            {
                break;
            }
        }

        node.emplace_back(node[*it].second, *active.rbegin());

        active.erase(*it);
        active.insert(i);

        state.push_back(state[id]);
    }

    for (int i = 1; i < (int)state.size(); i++)
    {
        cout << state[i] << '\n';
    }
    cout << '\n';

    return 0;
}

Compilation message (stderr)

edi.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
edi.cpp:43: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   43 | #pragma endregion
      |

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