Submission #802019

#	Time	Username	Problem	Language	Result	Execution time	Memory
802019		thimote75	Editor (BOI15_edi)	C++17	0 / 100	3075 ms	10420 KiB

edi

#include <bits/stdc++.h>

using namespace std;

string to_string (string s) { return s; }

template <typename T> string to_string (T A) {
    string str = "[";
    bool first = true;

    for (const auto &p : A) {
        if (!first) str += ", ";
        str += to_string(p);
        first = false;
    }

    str += "]";
    return str;
}
template<typename A, typename B> string to_string (pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void dbg_out () { cout << endl; }
template<typename Head, typename... Tail> void dbg_out (Head H, Tail... T) {
    cout << to_string(H) << " ";

    dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "): "; dbg_out(__VA_ARGS__);
#else
#define dbg(...)
#endif

using idata = vector<int>;
using bdata = vector<bool>;

using di  = pair<int, int>;
using vdi = vector<di>;

idata level;
idata state;
idata parent;

bdata active;

struct SegTree {
    idata tree;

    SegTree (int size) {
        tree.resize(size, 1e9);
    }

    int query (int left, int right) {
        int res = 1e9;

        for (int i = left; i <= right; i ++)
            res = min(res, tree[i]);
        
        return res;
    }
    void modify (int pos, int value) {
        tree[pos] = value;
    }
};

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

    int N;
    cin >> N;    

    level .resize(N + 1);
    state .resize(N + 1);
    parent.resize(N + 1, - 1);

    vdi sorted_pos;

    for (int i = 1; i <= N; i ++) {
        int x; cin >> x;

        level[i] = max(- x, 0);
        state[i] = max(x, 0);

        sorted_pos.push_back({ level[i], i });
    }

    sort(sorted_pos.begin(), sorted_pos.end());

    idata min_query_pos(N + 1, N + 1);
    idata set_query_idx(N + 1);

    int idx = 0;
    for (const auto &pos : sorted_pos) {
        int lev = pos.first;

        if (min_query_pos[lev] == N + 1)
            min_query_pos[lev] = idx;

        set_query_idx[pos.second] = idx ++;
    }

    SegTree tree(N + 1);

    active.resize(N + 1);
    for (int i = N; i >= 1; i --) {
        int qlev = level[i] + 1;
        active[i] = true;

        if (qlev <= N && min_query_pos[qlev] <= N) {
            while (true) {
                int local = tree.query( min_query_pos[qlev], N );
                if (local > N) break ;

                parent[local] = i;
                tree.modify(set_query_idx[local], 1e9);

                if (active[local]) {
                    active[i] = false;
                    break ;
                }
            }
        }

        tree.modify(set_query_idx[i], i);
    }

    for (int i = 1; i <= N; i ++) {
        if (level[i] != 0) {
            assert(parent[i] != -1);
            state[i] = state[parent[i] - 1];
        }

        cout << state[i] << endl;
    }
}

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