oj.uz

Submission #802913

# Submission time Handle Problem Language Result Execution time Memory
802913 2023-08-02T15:47:19 Z Arturgo Editor (BOI15_edi) C++14
100 / 100
 110 ms 34324 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;
}

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16720 KB Output is correct
2 Correct 10 ms 17032 KB Output is correct
3 Correct 9 ms 16692 KB Output is correct
4 Correct 9 ms 16772 KB Output is correct
5 Correct 10 ms 16980 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 11 ms 17044 KB Output is correct
8 Correct 9 ms 16716 KB Output is correct
9 Correct 11 ms 17052 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 34300 KB Output is correct
2 Correct 91 ms 34220 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 25404 KB Output is correct
2 Correct 57 ms 27216 KB Output is correct
3 Correct 88 ms 28588 KB Output is correct
4 Correct 86 ms 34324 KB Output is correct
5 Correct 91 ms 33968 KB Output is correct
6 Correct 71 ms 33856 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16720 KB Output is correct
2 Correct 10 ms 17032 KB Output is correct
3 Correct 9 ms 16692 KB Output is correct
4 Correct 9 ms 16772 KB Output is correct
5 Correct 10 ms 16980 KB Output is correct
6 Correct 9 ms 16724 KB Output is correct
7 Correct 11 ms 17044 KB Output is correct
8 Correct 9 ms 16716 KB Output is correct
9 Correct 11 ms 17052 KB Output is correct
10 Correct 87 ms 34300 KB Output is correct
11 Correct 91 ms 34220 KB Output is correct
12 Correct 52 ms 25404 KB Output is correct
13 Correct 57 ms 27216 KB Output is correct
14 Correct 88 ms 28588 KB Output is correct
15 Correct 86 ms 34324 KB Output is correct
16 Correct 91 ms 33968 KB Output is correct
17 Correct 71 ms 33856 KB Output is correct
18 Correct 97 ms 33412 KB Output is correct
19 Correct 89 ms 33860 KB Output is correct
20 Correct 96 ms 31284 KB Output is correct
21 Correct 92 ms 34224 KB Output is correct
22 Correct 110 ms 34032 KB Output is correct