제출 #1014740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1014740		canadavid1	Regions (IOI09_regions)	C++17	35 / 100	3875 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;
    
    const Node* n = nullptr;
    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);
    treap(const treap& o);
    void reset();
    treap& operator=(const treap& o);
    treap& operator=(treap&& o);
    ~treap();
    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;
    H pri;
    mutable int refct=0;
    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) {}
    Node(treap o, treap l,treap r) : key(o->key),val(o->val),pri(o->pri),l(l),r(r) {}
    Node(treap o, int val) : key(o->key),val(val),pri(o->pri),l(o->l),r(o->r) {}
};
template<typename... Args>
treap::Node* alloc(Args... args)
{
    return new treap::Node(args...);
}

treap::treap(const Node* n) : n(n) {n->refct++;}

void treap::reset() 
{
    if(!n) return;
    if(!--n->refct)
    {
        delete n;
    }
    n = nullptr;
}

treap& treap::operator=(const treap& o)
{
    reset();
    n = o.n;
    if(n) n->refct++;
    return *this;
}
treap& treap::operator=(treap&& o)
{
    reset();
    n = o.n;
    if(n) n->refct++;
    return *this;
}
treap::treap(const treap& o)
{
    n = o.n;
    if(n) n->refct++;
}
treap::~treap()
{
    reset();
}

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;
    }
    
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 85