oj.uz

Submission #802865

# Submission time Handle Problem Language Result Execution time Memory
802865 2023-08-02T15:18:06 Z Arturgo Editor (BOI15_edi) C++14
100 / 100
 128 ms 66448 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 10580 KB Output is correct
3 Correct 5 ms 9732 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 7 ms 10580 KB Output is correct
6 Correct 5 ms 9740 KB Output is correct
7 Correct 8 ms 10636 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 7 ms 10632 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 66448 KB Output is correct
2 Correct 116 ms 66396 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 37400 KB Output is correct
2 Correct 67 ms 43008 KB Output is correct
3 Correct 109 ms 54616 KB Output is correct
4 Correct 110 ms 66368 KB Output is correct
5 Correct 114 ms 65320 KB Output is correct
6 Correct 110 ms 63948 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 7 ms 10580 KB Output is correct
3 Correct 5 ms 9732 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 7 ms 10580 KB Output is correct
6 Correct 5 ms 9740 KB Output is correct
7 Correct 8 ms 10636 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 7 ms 10632 KB Output is correct
10 Correct 116 ms 66448 KB Output is correct
11 Correct 116 ms 66396 KB Output is correct
12 Correct 63 ms 37400 KB Output is correct
13 Correct 67 ms 43008 KB Output is correct
14 Correct 109 ms 54616 KB Output is correct
15 Correct 110 ms 66368 KB Output is correct
16 Correct 114 ms 65320 KB Output is correct
17 Correct 110 ms 63948 KB Output is correct
18 Correct 114 ms 65224 KB Output is correct
19 Correct 105 ms 64040 KB Output is correct
20 Correct 128 ms 65716 KB Output is correct
21 Correct 112 ms 66352 KB Output is correct
22 Correct 118 ms 65368 KB Output is correct