Submission #1098889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098889		Pacybwoah	Werewolf (IOI18_werewolf)	C++17	100 / 100	472 ms	92920 KiB

werewolf

#include "werewolf.h"
#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
using namespace std;
namespace{
    int n, q;
    vector<int> bases;
    struct node{
        int par, sz, lid, rid;
        node(int a, int b, int c, int d){
            par = a;
            sz = b;
            lid = c;
            rid = d;
        }
    };
    struct dsust{
        vector<node> dsu;
        vector<int> l, r, w, vec, pos;
        vector<vector<int>> st;
        dsust(){
            for(int i = 0; i <= n; i++) dsu.push_back(node(i, 1, i, i));
            l.resize(n + 1);
            r.resize(n + 1);
            w.resize(n + 1);
            vec.resize(n + 1);
            pos.resize(n + 1);
            st.resize(19, vector<int>(n + 1));
            fill(l.begin(), l.end(), -1);
            fill(r.begin(), r.end(), -1);
        }
        int query(int x){
            if(x == dsu[x].par) return x;
            dsu[x].par = query(dsu[x].par);
            return dsu[x].par;
        }
        void unite(int a, int b, int val){
            a = query(a);
            b = query(b);
            if(a == b) return;
            if(dsu[a].sz < dsu[b].sz) swap(a, b);
            dsu[b].par = a;
            dsu[a].sz += dsu[b].sz;
            w[dsu[a].rid] = val;
            r[dsu[a].rid] = dsu[b].lid;
            l[dsu[b].lid] = dsu[a].rid;
            dsu[a].rid = dsu[b].rid;
        }
        void build(){
            int cur = dsu[query(1)].lid;
            for(int i = 1; i <= n; i++){
                vec[i] = cur;
                pos[cur] = i;
                st[0][i] = w[cur];
                cur = r[cur];
            }
            for(int i = 1; i < 19; i++){
                for(int j = 1; j < n; j++){
                    st[i][j] = max(st[i - 1][j], st[i - 1][min(n - 1, j + (1 << (i - 1)))]);
                }
            }
        }
        int query(int ql, int qr){
            int len = qr - ql + 1;
            return max(st[bases[len]][ql], st[bases[len]][qr - (1 << bases[len]) + 1]);
        }
        pair<int, int> get_rng(int id, int val){
            pair<int, int> ans;
            id = pos[id];
            int bsl = id, bsr = n;
            while(bsl < bsr){
                int mid = ((bsl + bsr) >> 1) + 1;
                if(query(id, mid - 1) > val) bsr = mid - 1;
                else bsl = mid;
            }
            ans.second = bsl;
            bsl = 1, bsr = id;
            while(bsl < bsr){
                int mid = (bsl + bsr) >> 1;
                if(query(mid, id - 1) > val) bsl = mid + 1;
                else bsr = mid;
            }
            ans.first = bsl;
            return ans;
        }
    };
    struct bit{
        vector<int> vec;
        bit(int _n){
            vec.resize(_n + 1);
        }
        void modify(int pos){
            while(pos <= n){
                vec[pos]++;
                pos += (pos & -pos);
            }
        }
        int query(int pos){
            int ans = 0;
            while(pos > 0){
                ans += vec[pos];
                pos -= (pos & -pos);
            }
            return ans;
        }
    };
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
    n = N;
    q = (int)S.size();
    bases.resize(n);
    int now = 0;
    for(int i = 1; i < n; i++){
        if((1 << (now + 1)) <= i) now++;
        bases[i] = now;
    }
    int m = (int)X.size();
    vector<pair<pair<int, int>, int>> maxedges, minedges;
    auto cmp = [&](pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
        return a.second < b.second;
    };
    for(int i = 0; i < m; i++){
        X[i]++;
        Y[i]++;
        maxedges.push_back(make_pair(make_pair(X[i], Y[i]), -min(X[i], Y[i])));
        minedges.push_back(make_pair(make_pair(X[i], Y[i]), max(X[i], Y[i])));
    }
    sort(maxedges.begin(), maxedges.end(), cmp);
    sort(minedges.begin(), minedges.end(), cmp);
    dsust maxst = dsust(), minst = dsust();
    for(auto &[x, val]: maxedges){
        auto &[u, v] = x;
        maxst.unite(u, v, val);
    }
    for(auto &[x, val]: minedges){
        auto &[u, v] = x;
        minst.unite(u, v, val);
    }
    maxst.build();
    minst.build();
    vector<pair<int, int>> qpos(q);
    vector<vector<pair<int, int>>> sweep(n + 1);
    vector<int> ans(q);
    for(int i = 0; i < q; i++){
        S[i]++;
        E[i]++;
        L[i]++;
        R[i]++;
        qpos[i] = minst.get_rng(E[i], R[i]);
        auto [l, r] = maxst.get_rng(S[i], -L[i]);
        sweep[l - 1].emplace_back(i, -1);
        sweep[r].emplace_back(i, 1);
    }
    bit b(n);
    for(int i = 1; i <= n; i++){
        b.modify(minst.pos[maxst.vec[i]]);
        for(auto &[id, val]: sweep[i]){
            ans[id] += val * (b.query(qpos[id].second) - b.query(qpos[id].first - 1));
        }
    }
    vector<int> anss;
    for(int i = 0; i < q; i++){
        if(ans[i] > 0) anss.push_back(1);
        else anss.push_back(0);
    }
    return anss;
}
// g++ -std=c++17 -fsanitize=undefined -fsanitize=address -Wall -Wextra -Wshadow grader.cpp werewolf.cpp -o run
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51