Submission #802865

#	Time	Username	Problem	Language	Result	Execution time	Memory
802865		Arturgo	Editor (BOI15_edi)	C++14	100 / 100	128 ms	66448 KiB

edi

#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct Node {
    T data;
    vector<Node<T>*> children;
};

template<typename T>
Node<T>* merge(Node<T>* a, Node<T>* b) {
    if(a->data > b->data) {
        a->children.push_back(b);
        return a;
    }
    b->children.push_back(a);
    return b;
}

const int N_BITS = 20;

template<typename T>
using Heap = array<Node<T>*, N_BITS>;

template<typename T>
Heap<T> merge(Heap<T>& a, Heap<T>& b) {
    Node<T>* reste = NULL;
    
    Heap<T> nouv;
    nouv.fill(NULL);
    
    for(int iBit = 0;iBit < N_BITS;iBit++) {
        if(reste == NULL) {
            if(a[iBit] == NULL)
                nouv[iBit] = b[iBit];
            else if(b[iBit] == NULL)
                nouv[iBit] = a[iBit];
            else
                reste = merge(a[iBit], b[iBit]);
        }
        else {
            if(a[iBit] == NULL && b[iBit] == NULL) {
                nouv[iBit] = reste;
                reste = NULL;
            }
            else if(b[iBit] == NULL) {
                nouv[iBit] = merge(reste, a[iBit]);
                reste = NULL;
            }
            else if(a[iBit] == NULL) {
                nouv[iBit] = merge(reste, b[iBit]);
                reste = NULL;
            }
            else {
                nouv[iBit] = reste;
                reste = merge(a[iBit], b[iBit]);
            }
        }
    }
    
    return nouv;
}

pair<int, int> def = {-1e8, -1e8};

 
const int N = 3e5 + 42;
int iNode = 0;
Node<pair<int, int>> nodes[N];

template<typename T>
T top(Heap<T>& a) {
    T opt = def;
    
    for(int iBit = 0;iBit < N_BITS;iBit++) {
        if(a[iBit] != NULL) {
            if(a[iBit]->data > opt) {
                opt = a[iBit]->data;
            }
        }
    }
    
    return opt;
}
 
template<typename T>
void pop(Heap<T>& a) {
    T opt = def;
    int bitOpt = -1;
    
    for(int iBit = 0;iBit < N_BITS;iBit++) {
        if(a[iBit] != NULL) {
            if(a[iBit]->data > opt) {
                opt = a[iBit]->data;
                bitOpt = iBit;
            }
        }
    }
    
    Heap<T> nouv;
    nouv.fill(NULL);
    
    for(int iChild = 0;iChild < (int)a[bitOpt]->children.size();iChild++) {
        nouv[iChild] = a[bitOpt]->children[iChild];
    }
    a[bitOpt] = NULL;

    a = merge(a, nouv);
}

template<typename T>
void push(Heap<T>& a, T elem) {
    Node<T>* n = nodes + iNode;
    iNode++;
    n->data = elem;
    
    for(int iBit = 0;iBit < N_BITS;iBit++) {
        if(a[iBit] == NULL) {
            a[iBit] = n;
            break;
        }
        n = merge(n, a[iBit]);
    }
}
 
int n, lvl[N], par[N], val[N];
Heap<pair<int, int>> hid[N];
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> lvl[i];
        lvl[i] = -lvl[i];
    }
 
    Heap<pair<int, int>> cur, nxt;
    cur.fill(NULL);
    nxt.fill(NULL);
    
    for(int i = n-1; i > -1; i--) {
        par[i] = i;
        
        swap(cur, nxt);
        nxt.fill(NULL);
        
        push(nxt, {max(lvl[i], 0), i});
        
        while(true) {
            pair<int, int> p = top(cur);
            if(p.first <= max(lvl[i], 0))
                break;
            int id = p.second;
            pop(cur);
            
            par[id] = i;
            nxt = merge(nxt, hid[id]);
        }
        
        swap(cur, hid[i]);
    }
    
    for(int i = 0; i < n; i++) {
        if(lvl[i] < 0)
            cout << (val[i] = -lvl[i]) << '\n';
        else if(par[i] == 0) {
            cout << 0 << '\n';
        }
        else {
            cout << (val[i] = val[par[i]-1]) << '\n';
        }
    }
}

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