oj.uz

Submission #1014735

# Submission time Handle Problem Language Result Execution time Memory
1014735 2024-07-05T11:39:54 Z canadavid1 Regions (IOI09_regions) C++17
30 / 100
 4200 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);
    }

    // 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 340 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 6 ms 856 KB Output is correct
6 Correct 25 ms 4696 KB Output is correct
7 Correct 32 ms 2648 KB Output is correct
8 Correct 53 ms 4696 KB Output is correct
9 Correct 221 ms 13580 KB Output is correct
10 Correct 373 ms 20304 KB Output is correct
11 Correct 721 ms 20664 KB Output is correct
12 Correct 1847 ms 39248 KB Output is correct
13 Correct 410 ms 22352 KB Output is correct
14 Correct 1062 ms 29776 KB Output is correct
15 Correct 1424 ms 41044 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2967 ms 50768 KB Output is correct
2 Correct 3397 ms 51276 KB Output is correct
3 Correct 4200 ms 74832 KB Output is correct
4 Runtime error 1188 ms 131072 KB Execution killed with signal 9
5 Runtime error 290 ms 131072 KB Execution killed with signal 9
6 Runtime error 1435 ms 131072 KB Execution killed with signal 9
7 Runtime error 409 ms 131072 KB Execution killed with signal 9
8 Runtime error 154 ms 131072 KB Execution killed with signal 9
9 Runtime error 154 ms 131072 KB Execution killed with signal 9
10 Runtime error 142 ms 131072 KB Execution killed with signal 9
11 Runtime error 168 ms 131072 KB Execution killed with signal 9
12 Runtime error 162 ms 131072 KB Execution killed with signal 9
13 Runtime error 147 ms 131072 KB Execution killed with signal 9
14 Runtime error 160 ms 131072 KB Execution killed with signal 9
15 Runtime error 147 ms 131072 KB Execution killed with signal 9
16 Runtime error 143 ms 131072 KB Execution killed with signal 9
17 Runtime error 149 ms 131072 KB Execution killed with signal 9