oj.uz

Submission #802831

# Submission time Handle Problem Language Result Execution time Memory
802831 2023-08-02T14:54:03 Z Arturgo Editor (BOI15_edi) C++14
63 / 100
 141 ms 60216 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 = 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 4 ms 1236 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 60160 KB Output is correct
2 Correct 141 ms 60216 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 29372 KB Output is correct
2 Correct 66 ms 35172 KB Output is correct
3 Correct 110 ms 45164 KB Output is correct
4 Correct 116 ms 60192 KB Output is correct
5 Correct 120 ms 59960 KB Output is correct
6 Correct 128 ms 60132 KB Output is correct

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 1236 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 4 ms 1236 KB Output is correct
10 Correct 116 ms 60160 KB Output is correct
11 Correct 141 ms 60216 KB Output is correct
12 Correct 58 ms 29372 KB Output is correct
13 Correct 66 ms 35172 KB Output is correct
14 Correct 110 ms 45164 KB Output is correct
15 Correct 116 ms 60192 KB Output is correct
16 Correct 120 ms 59960 KB Output is correct
17 Correct 128 ms 60132 KB Output is correct
18 Incorrect 120 ms 58672 KB Output isn't correct
19 Halted 0 ms 0 KB -