oj.uz

Submission #1014737

# Submission time Handle Problem Language Result Execution time Memory
1014737 2024-07-05T11:41:53 Z canadavid1 Regions (IOI09_regions) C++17
30 / 100
 4581 ms 131072 KB 
#include <iostream>
#include <vector>
#include <random>
#include <array>
#include <memory>

auto rng = std::mt19937(std::random_device()());
struct treap
{
    using H = decltype(rng)::result_type;
    struct Node;
    
    std::shared_ptr<const Node> n;
    operator bool() const {return !!n;}
    const Node &operator*() const {return *n;}
    const Node *operator->() const {return &*n;}
    treap(std::nullptr_t v=nullptr) : n(nullptr) {}
    treap(const Node*p) : n(p) {}
    std::array<treap,3> split(int key) const;
    treap insert(int key, int val,H pri=0) const;
    int operator[](int key) const;
    treap add(int key, int inc) const
    {
        return insert(key,operator[](key)+inc,0);
    }
};
struct treap::Node
{
    int key;
    int val;
    int size;
    H pri;
    treap l,r;
    Node() {}
    Node(int key, int val,H pri,treap l,treap r) : key(key),val(val),pri(pri),l(l),r(r),
        size(1 + (l ? l->size : 0) + (r ? r->size : 0)) {}
    Node(treap o, treap l,treap r) : key(o->key),val(o->val),pri(o->pri),l(l),r(r),
        size(1 + (l ? l->size : 0) + (r ? r->size : 0)) {}
    Node(treap o, int val) : key(o->key),val(val),pri(o->pri),l(o->l),r(o->r),
        size(o->size) {}
};
template<typename... Args>
treap::Node* alloc(Args... args)
{
    return new treap::Node(args...);
}

std::array<treap,3> treap::split(int key) const
{
    if(!n) return {};
    if(n->key == key) return {n->l,alloc(*this,nullptr,nullptr),n->r};
    if(key < n->key)
    {
        auto[Lp,m,Rp] = n->l.split(key);
        return {Lp,m,alloc(*this,Rp,n->r)};
    }
    else
    {
        auto[Lp,m,Rp] = n->r.split(key);
        return {alloc(*this,n->l,Lp),m,Rp};
    }
}
treap treap::insert(int key, int val,H pri) const
{
    while(!pri) pri = rng();
    if(!n) return alloc(key,val,pri,nullptr,nullptr);
    if(n->key == key)
    {
        return alloc(*this,val);
    }
    if(pri > n->pri)
    {
        auto[l,m,r] = split(key);
        return alloc(key,val,pri,l,r);
    }
    auto d = n->key < key;
    treap c[2] {n->l,n->r};
    c[d] = c[d].insert(key,val,pri);
    return alloc(*this,c[0],c[1]);
}
int treap::operator[](int key) const
{
    if(!n) return 0;
    if(n->key == key) return n->val;
    if(key < n->key) return n->l[key];
    else return n->r[key];
}

treap unite(treap a,treap b) // O(m log(n/m)) where m <= n are sizes
{
    if(!a) return b;
    if(!b) return a;
    if(a->pri > b->pri) std::swap(a,b);
    auto[L,m,R] = a.split(b->key);
    return alloc(b->key,b->val + (m ? m->val : 0),b->pri,
        unite(b->l,L),unite(b->r,R));
}

struct employee
{
    int par=0;
    int region;
    treap here_up;
};

int main()
{
    std::cin.tie(0)->sync_with_stdio(0);
    int N,R,Q;
    std::cin >> N >> R >> Q;
    std::vector<employee> employees(N);
    for(auto& i : employees)
    {
        if(&i!=employees.data()) std::cin >> i.par;
        std::cin >> i.region;
        i.par--;
    }
    
    for(auto& i : employees)
    {
        if(i.par >= 0)
        {
            i.here_up = employees[i.par].here_up;
        }
        i.here_up = i.here_up.add(i.region,1);
    }
    std::vector<treap> for_each(R+1);
    for(int i = employees.size()-1; i >= 0; i--)
    {
        auto& j = employees[i];
        for_each[j.region] = unite(for_each[j.region],j.here_up);
        j.here_up = nullptr;
    }

    // online queries :-(
    for (int _ = 0; _ < Q; _++)
    {
        int r1,r2;
        std::cin >> r1 >> r2;

        std::cout << for_each[r2][r1] << "\n" << std::flush;
    }
    
}

Compilation message

regions.cpp: In constructor 'treap::Node::Node(int, int, treap::H, treap, treap)':
regions.cpp:33:13: warning: 'treap::Node::r' will be initialized after [-Wreorder]
   33 |     treap l,r;
      |             ^
regions.cpp:31:9: warning:   'int treap::Node::size' [-Wreorder]
   31 |     int size;
      |         ^~~~
regions.cpp:35:5: warning:   when initialized here [-Wreorder]
   35 |     Node(int key, int val,H pri,treap l,treap r) : key(key),val(val),pri(pri),l(l),r(r),
      |     ^~~~
regions.cpp: In constructor 'treap::Node::Node(treap, treap, treap)':
regions.cpp:33:13: warning: 'treap::Node::r' will be initialized after [-Wreorder]
   33 |     treap l,r;
      |             ^
regions.cpp:31:9: warning:   'int treap::Node::size' [-Wreorder]
   31 |     int size;
      |         ^~~~
regions.cpp:37:5: warning:   when initialized here [-Wreorder]
   37 |     Node(treap o, treap l,treap r) : key(o->key),val(o->val),pri(o->pri),l(l),r(r),
      |     ^~~~
regions.cpp: In constructor 'treap::Node::Node(treap, int)':
regions.cpp:33:13: warning: 'treap::Node::r' will be initialized after [-Wreorder]
   33 |     treap l,r;
      |             ^
regions.cpp:31:9: warning:   'int treap::Node::size' [-Wreorder]
   31 |     int size;
      |         ^~~~
regions.cpp:39:5: warning:   when initialized here [-Wreorder]
   39 |     Node(treap o, int val) : key(o->key),val(val),pri(o->pri),l(o->l),r(o->r),
      |     ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 6 ms 808 KB Output is correct
6 Correct 30 ms 4440 KB Output is correct
7 Correct 35 ms 2136 KB Output is correct
8 Correct 58 ms 3672 KB Output is correct
9 Correct 226 ms 11848 KB Output is correct
10 Correct 370 ms 14344 KB Output is correct
11 Correct 744 ms 18768 KB Output is correct
12 Correct 2052 ms 37424 KB Output is correct
13 Correct 399 ms 16464 KB Output is correct
14 Correct 1037 ms 27728 KB Output is correct
15 Correct 1446 ms 40504 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3065 ms 49060 KB Output is correct
2 Correct 3394 ms 60508 KB Output is correct
3 Correct 4581 ms 72196 KB Output is correct
4 Runtime error 1573 ms 131072 KB Execution killed with signal 9
5 Runtime error 320 ms 131072 KB Execution killed with signal 9
6 Runtime error 1614 ms 131072 KB Execution killed with signal 9
7 Runtime error 498 ms 131072 KB Execution killed with signal 9
8 Runtime error 163 ms 131072 KB Execution killed with signal 9
9 Runtime error 156 ms 131072 KB Execution killed with signal 9
10 Runtime error 147 ms 131072 KB Execution killed with signal 9
11 Runtime error 156 ms 131072 KB Execution killed with signal 9
12 Runtime error 182 ms 131072 KB Execution killed with signal 9
13 Runtime error 164 ms 131072 KB Execution killed with signal 9
14 Runtime error 157 ms 131072 KB Execution killed with signal 9
15 Runtime error 170 ms 131072 KB Execution killed with signal 9
16 Runtime error 159 ms 131072 KB Execution killed with signal 9
17 Runtime error 144 ms 131072 KB Execution killed with signal 9