제출 #802831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802831		Arturgo	Editor (BOI15_edi)	C++14	63 / 100	141 ms	60216 KiB

edi

#include <bits/stdc++.h>
#define int long long
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 = 18;

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};

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];
    }
    delete a[bitOpt];
    a[bitOpt] = NULL;

    a = merge(a, nouv);
}

template<typename T>
void push(Heap<T>& a, T elem) {
    Heap<T> nouv;
    nouv.fill(NULL);
    
    Node<T>* n = new Node<T>();
    n->data = elem;
    nouv[0] = n;
    
    a = merge(a, nouv);
}
 
const int N = 3e5 + 42, INF = 1e18 + 42;
 
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;
        
        cur = nxt;
        nxt = Heap<pair<int, int>>();
        nxt.fill(NULL);
        
        push(nxt, {max(lvl[i], 0ll), i});
        
        while(true) {
            pair<int, int> p = top(cur);
            if(p.first <= max(lvl[i], 0ll))
                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: 0 / 37