Submission #1014737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014737		canadavid1	Regions (IOI09_regions)	C++17	30 / 100	4581 ms	131072 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 15 / 85