Submission #802913

#	Time	Username	Problem	Language	Result	Execution time	Memory
802913		Arturgo	Editor (BOI15_edi)	C++14	100 / 100	110 ms	34324 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;
}

template<typename T>
using Heap = vector<Node<T>*>;

template<typename T>
inline Node<T>* get(Heap<T>& a, int idx) {
    if(idx >= (int)a.size()) return NULL;
    return a[idx];
}

template<typename T>
Heap<T> merge(Heap<T>& a, Heap<T>& b) {
    Node<T>* reste = NULL;
    
    Heap<T> nouv;
    
    for(int iBit = 0;iBit < (int)max(a.size(), b.size());iBit++) {
        if(reste == NULL) {
            if(get(a, iBit) == NULL)
                nouv.push_back(get(b, iBit));
            else if(get(b, iBit) == NULL)
                nouv.push_back(get(a, iBit));
            else {
                nouv.push_back(NULL);
                reste = merge(get(a, iBit), get(b, iBit));
            }
        }
        else {
            if(get(a, iBit) == NULL && get(b, iBit) == NULL) {
                nouv.push_back(reste);
                reste = NULL;
            }
            else if(get(b, iBit) == NULL) {
                nouv.push_back(merge(reste, get(a, iBit)));
                reste = NULL;
            }
            else if(get(a, iBit) == NULL) {
                nouv.push_back(merge(reste, get(b, iBit)));
                reste = NULL;
            }
            else {
                nouv.push_back(reste);
                reste = merge(get(a, iBit), get(b, iBit));
            }
        }
    }
    
    if(reste != NULL)
        nouv.push_back(reste);
    
    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 < (int)a.size();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 < (int)a.size();iBit++) {
        if(a[iBit] != NULL) {
            if(a[iBit]->data > opt) {
                opt = a[iBit]->data;
                bitOpt = iBit;
            }
        }
    }
    
    Heap<T> nouv;
    swap(nouv, a[bitOpt]->children);
    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 < (int)a.size();iBit++) {
        if(a[iBit] == NULL) {
            a[iBit] = n;
            return;
        }
        n = merge(n, a[iBit]);
    }
    
    a.push_back(n);
}
 
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;
    
    for(int i = n-1; i > -1; i--) {
        par[i] = i;
        
        swap(cur, nxt);
        nxt.clear();
        
        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