oj.uz

Submission #802857

# Submission time Handle Problem Language Result Execution time Memory
802857 2023-08-02T15:13:31 Z Arturgo Editor (BOI15_edi) C++14
100 / 100
 134 ms 72020 KB 
#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 = 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;
        
        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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 13012 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 6 ms 12008 KB Output is correct
5 Correct 7 ms 13012 KB Output is correct
6 Correct 5 ms 11988 KB Output is correct
7 Correct 8 ms 13012 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 7 ms 13012 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 72012 KB Output is correct
2 Correct 134 ms 72020 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 41264 KB Output is correct
2 Correct 62 ms 47220 KB Output is correct
3 Correct 96 ms 59480 KB Output is correct
4 Correct 103 ms 71932 KB Output is correct
5 Correct 114 ms 70940 KB Output is correct
6 Correct 87 ms 69528 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 13012 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 6 ms 12008 KB Output is correct
5 Correct 7 ms 13012 KB Output is correct
6 Correct 5 ms 11988 KB Output is correct
7 Correct 8 ms 13012 KB Output is correct
8 Correct 5 ms 11988 KB Output is correct
9 Correct 7 ms 13012 KB Output is correct
10 Correct 103 ms 72012 KB Output is correct
11 Correct 134 ms 72020 KB Output is correct
12 Correct 55 ms 41264 KB Output is correct
13 Correct 62 ms 47220 KB Output is correct
14 Correct 96 ms 59480 KB Output is correct
15 Correct 103 ms 71932 KB Output is correct
16 Correct 114 ms 70940 KB Output is correct
17 Correct 87 ms 69528 KB Output is correct
18 Correct 104 ms 70872 KB Output is correct
19 Correct 98 ms 69740 KB Output is correct
20 Correct 128 ms 71392 KB Output is correct
21 Correct 103 ms 71996 KB Output is correct
22 Correct 107 ms 70856 KB Output is correct