oj.uz

Submission #802848

# Submission time Handle Problem Language Result Execution time Memory
802848 2023-08-02T15:09:25 Z Arturgo Editor (BOI15_edi) C++14
100 / 100
 136 ms 72056 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) {
    Heap<T> nouv;
    nouv.fill(NULL);
    
    Node<T>* n = nodes + iNode;
    iNode++;
    n->data = elem;
    nouv[0] = n;
    
    a = merge(a, nouv);
}
 
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 5 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 5 ms 11988 KB Output is correct
5 Correct 7 ms 13012 KB Output is correct
6 Correct 5 ms 11988 KB Output is correct
7 Correct 7 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 118 ms 72056 KB Output is correct
2 Correct 128 ms 71988 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 41304 KB Output is correct
2 Correct 71 ms 47220 KB Output is correct
3 Correct 107 ms 59476 KB Output is correct
4 Correct 119 ms 72016 KB Output is correct
5 Correct 118 ms 70856 KB Output is correct
6 Correct 101 ms 69556 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 ms 11988 KB Output is correct
5 Correct 7 ms 13012 KB Output is correct
6 Correct 5 ms 11988 KB Output is correct
7 Correct 7 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 118 ms 72056 KB Output is correct
11 Correct 128 ms 71988 KB Output is correct
12 Correct 64 ms 41304 KB Output is correct
13 Correct 71 ms 47220 KB Output is correct
14 Correct 107 ms 59476 KB Output is correct
15 Correct 119 ms 72016 KB Output is correct
16 Correct 118 ms 70856 KB Output is correct
17 Correct 101 ms 69556 KB Output is correct
18 Correct 120 ms 70856 KB Output is correct
19 Correct 110 ms 69760 KB Output is correct
20 Correct 136 ms 71288 KB Output is correct
21 Correct 117 ms 71940 KB Output is correct
22 Correct 118 ms 70860 KB Output is correct