Submission #559474

#	Time	Username	Problem	Language	Result	Execution time	Memory
559474		emuyumi	Teams (IOI15_teams)	C++17	77 / 100	4108 ms	175576 KiB

teams

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Segtree{

#define mid ((l + r) >> 1)

    struct Node{
        int lc, rc, val;
    };

    int N;
    vector<Node> st;
    int T;

    Segtree() = default;
    Segtree(int N) : N(N) {
        st.resize(25 * N);
        T = 0;

        build(0, 1, N);
    }

    int build(int v, int l, int r){
        if (l == r) return v;
        st[v].lc = build(++T, l, mid);
        st[v].rc = build(++T, mid + 1, r);
        return v;
    }

    int insert(int v, int l, int r, int idx){
        int nv = ++T;
        if (l == r){
            st[nv] = {0, 0, st[v].val + 1};
        }
        else if (idx <= mid){
            st[nv].lc = insert(st[v].lc, l, mid, idx);
            st[nv].rc = st[v].rc;
            st[nv].val = st[st[nv].lc].val + st[st[nv].rc].val;
        }
        else{
            st[nv].lc = st[v].lc;
            st[nv].rc = insert(st[v].rc, mid + 1, r, idx);
            st[nv].val = st[st[nv].lc].val + st[st[nv].rc].val;
        }
        return nv;
    }
    int insert(int v, int idx){ return insert(v, 1, N, idx); }

    int query(int v, int l, int r, int ql, int qr){
        if (l > qr || r < ql || ql > qr) return 0;
        if (l >= ql && r <= qr) return st[v].val;
        return query(st[v].lc, l, mid, ql, qr) + 
               query(st[v].rc, mid + 1, r, ql, qr);
    }
    int query(int v, int ql, int qr){ return query(v, 1, N, ql, qr); }

#undef mid
};

Segtree st;
vector<int> rts;

int N;

void init(int N, int A[], int B[]){
    ::N = N;
    st = Segtree(N);
    rts.resize(N + 1);
    int v = 0;

    vector<vector<int>> xs(N + 1);
    for (int i = 0; i < N; ++i){
        xs[A[i]].push_back(B[i]);
    }

    for (int i = 1; i <= N; ++i){
        rts[i] = rts[i - 1];
        for (int y : xs[i]){
            v = st.insert(v, y);
            rts[i] = v;
        }
    }
}

int count(int x1, int x2, int y1, int y2){
    if (x1 == 0) return st.query(rts[x2], y1, y2);
    return st.query(rts[x2], y1, y2) - st.query(rts[x1 - 1], y1, y2);
}

mt19937 gen;

struct Treap{

    struct Node{
        int p, key, val, tot, sz;
        Node *lc, *rc;
        Node(int key, int val) : p(gen()), key(key), val(val), tot(val), sz(1), lc(0), rc(0) {}
    } *rt = 0;

    Treap() : rt(0) {}

    int get_sz(Node *v){ return v ? v->sz : 0; }
    int get_tot(Node *v){ return v ? v->tot : 0; }

    void pull(Node *v){
        if (v){
            v->tot = v->val + get_tot(v->lc) + get_tot(v->rc);
            v->sz = 1 + get_sz(v->lc) + get_sz(v->rc);
        }
    }

    void split(Node *v, Node *&l, Node *&r, int key){
        if (!v) return void(l = r = 0);
        if (v->key <= key) split(v->rc, v->rc, r, key), l = v;
        else split(v->lc, l, v->lc, key), r = v;
        pull(l); pull(r);
    }

    void merge(Node *&v, Node *l, Node *r){
        if (!l || !r) return void(v = l ? l : r);
        if (l->p > r->p) merge(l->rc, l->rc, r), v = l;
        else merge(r->lc, l, r->lc), v = r;
        pull(v);
    }

    void set(int key, int val){
        Node *t1, *t2, *t3;
        split(rt, t2, t3, key);
        split(t2, t1, t2, key - 1);
        assert(get_sz(t2));
        t2->val = t2->tot = val;
        merge(rt, t1, t2);
        merge(rt, rt, t3);
    }

    void insert(int key, int val){
        Node *t1, *t2, *t3;
        split(rt, t2, t3, key);
        split(t2, t1, t2, key - 1);
        Node *nd = new Node(key, val);
        merge(t1, t1, nd);
        merge(t3, t2, t3);
        merge(rt, t1, t3);
    }

    int sum_leq(int key){
        Node *t1;
        split(rt, t1, rt, key);
        int ret = get_tot(t1);
        merge(rt, t1, rt);
        return ret;
    }

    void rem_leq(int key){
        Node *t1;
        split(rt, t1, rt, key);
    }

    void print(Node *v){
        if (v->lc) print(v->lc);
        cout << v->key << " ";
        if (v->rc) print(v->rc);
    }
};

int can(int M, int K[]){
    sort(K, K + M);
    struct Item{
        int y, x, left;
        bool operator<(const Item &other) const{
            return y < other.y; 
        }
    };
    

    deque<Item> dq;
    dq.push_front({N + 1, 0, 0});

    Treap t{}; t.rt = 0;
    t.insert(N + 1, 0);

    // query number of unused points bounded by
    // corners (x, y) and (k, y - 1)
    //  ......
    // y**....
    //  *****.
    //  *****.
    //   x  k
    auto query = [&](int x, int y, int k){
        int add = count(0, x, y, y) + count(0, k, 0, y - 1);
        auto it = upper_bound(dq.begin(), dq.end(), Item{y, 0, 0});
        auto [hy, hx, _] = *it;
        int ly = (it == dq.begin() ? 0 : (--it)->y);
        int sub = count(0, hx, ly + 1, y) + t.sum_leq(y);
        return add - sub;
    };

    for (int i = 0; i < M; ++i){

        // delete corners with y < K[i]
        while (dq.front().y < K[i]){
            dq.pop_front();
        }
        t.rem_leq(K[i] - 1);
        t.insert(K[i] - 1, count(0, K[i], 0, K[i] - 1));
        auto [uy, ux, uleft] = dq.front();
        t.set(uy, count(0, ux, K[i], uy) - uleft);
        dq.push_front({K[i] - 1, K[i], 0});

        // bsearch y
        int lo = K[i], hi = N;
        while (lo < hi){
            int mi = (lo + hi) >> 1;
            if (query(K[i], mi, K[i]) >= K[i]) hi = mi;
            else lo = mi + 1;
        }
        int y = lo;

        // bsearch x
        lo = 1, hi = K[i];
        while (lo < hi){
            int mi = (lo + hi) >> 1;
            if (query(mi, y, K[i]) >= K[i]) hi = mi;
            else lo = mi + 1;
        }
        int x = hi;


        int mates = query(x, y, K[i]);
        // impossible
        if (mates < K[i]){
            return 0;
        }

        // update corners
        int hx, hy, hleft;
        while (true){
            hy = dq.front().y;
            hx = dq.front().x;
            hleft = dq.front().left;
            dq.pop_front();
            if (hy > y) break;
        }
        t.rem_leq(hy);
        t.insert(hy, count(0, hx, y + 1, hy) - hleft);
        int left = (mates - K[i]);
        t.insert(y, count(0, x, y, y) - left);
        t.insert(y - 1, count(0, K[i], 0, y - 1));

        dq.push_front({hy, hx, hleft});
        dq.push_front({y, x, left});
        dq.push_front({y - 1, K[i]});


    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In constructor 'Segtree::Segtree(int)':
teams.cpp:19:17: warning: declaration of 'N' shadows a member of 'Segtree' [-Wshadow]
   19 |     Segtree(int N) : N(N) {
      |             ~~~~^
teams.cpp:14:9: note: shadowed declaration is here
   14 |     int N;
      |         ^
teams.cpp: In constructor 'Segtree::Segtree(int)':
teams.cpp:19:17: warning: declaration of 'N' shadows a member of 'Segtree' [-Wshadow]
   19 |     Segtree(int N) : N(N) {
      |             ~~~~^
teams.cpp:14:9: note: shadowed declaration is here
   14 |     int N;
      |         ^
teams.cpp: In constructor 'Segtree::Segtree(int)':
teams.cpp:19:17: warning: declaration of 'N' shadows a member of 'Segtree' [-Wshadow]
   19 |     Segtree(int N) : N(N) {
      |             ~~~~^
teams.cpp:14:9: note: shadowed declaration is here
   14 |     int N;
      |         ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:68:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   68 | void init(int N, int A[], int B[]){
      |           ~~~~^
teams.cpp:66:5: note: shadowed declaration is here
   66 | int N;
      |     ^
teams.cpp: In constructor 'Treap::Node::Node(int, int)':
teams.cpp:100:27: warning: declaration of 'val' shadows a member of 'Treap::Node' [-Wshadow]
  100 |         Node(int key, int val) : p(gen()), key(key), val(val), tot(val), sz(1), lc(0), rc(0) {}
      |                       ~~~~^~~
teams.cpp:98:21: note: shadowed declaration is here
   98 |         int p, key, val, tot, sz;
      |                     ^~~
teams.cpp:100:18: warning: declaration of 'key' shadows a member of 'Treap::Node' [-Wshadow]
  100 |         Node(int key, int val) : p(gen()), key(key), val(val), tot(val), sz(1), lc(0), rc(0) {}
      |              ~~~~^~~
teams.cpp:98:16: note: shadowed declaration is here
   98 |         int p, key, val, tot, sz;
      |                ^~~
teams.cpp:100:39: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  100 |         Node(int key, int val) : p(gen()), key(key), val(val), tot(val), sz(1), lc(0), rc(0) {}
      |                                    ~~~^~
teams.cpp: In constructor 'Treap::Node::Node(int, int)':
teams.cpp:100:27: warning: declaration of 'val' shadows a member of 'Treap::Node' [-Wshadow]
  100 |         Node(int key, int val) : p(gen()), key(key), val(val), tot(val), sz(1), lc(0), rc(0) {}
      |                       ~~~~^~~
teams.cpp:98:21: note: shadowed declaration is here
   98 |         int p, key, val, tot, sz;
      |                     ^~~
teams.cpp:100:18: warning: declaration of 'key' shadows a member of 'Treap::Node' [-Wshadow]
  100 |         Node(int key, int val) : p(gen()), key(key), val(val), tot(val), sz(1), lc(0), rc(0) {}
      |              ~~~~^~~
teams.cpp:98:16: note: shadowed declaration is here
   98 |         int p, key, val, tot, sz;
      |                ^~~
teams.cpp: In constructor 'Treap::Node::Node(int, int)':
teams.cpp:100:27: warning: declaration of 'val' shadows a member of 'Treap::Node' [-Wshadow]
  100 |         Node(int key, int val) : p(gen()), key(key), val(val), tot(val), sz(1), lc(0), rc(0) {}
      |                       ~~~~^~~
teams.cpp:98:21: note: shadowed declaration is here
   98 |         int p, key, val, tot, sz;
      |                     ^~~
teams.cpp:100:18: warning: declaration of 'key' shadows a member of 'Treap::Node' [-Wshadow]
  100 |         Node(int key, int val) : p(gen()), key(key), val(val), tot(val), sz(1), lc(0), rc(0) {}
      |              ~~~~^~~
teams.cpp:98:16: note: shadowed declaration is here
   98 |         int p, key, val, tot, sz;
      |                ^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:255:36: warning: missing initializer for member 'can(int, int*)::Item::left' [-Wmissing-field-initializers]
  255 |         dq.push_front({y - 1, K[i]});
      |                                    ^

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23