oj.uz

Submission #828951

# Submission time Handle Problem Language Result Execution time Memory
828951 2023-08-17T21:29:00 Z Josia Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 93692 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;


int N, M, Q;
vector<vector<int>> graph;
vector<int> human, wolf;

void makeArrays() {
    human.clear();
    wolf.clear();

    {
        priority_queue<int, vector<int>, greater<int>> pq;
        pq.push(0);

        vector<bool> vis(N);

        while (pq.size()) {
            int v = pq.top();
            pq.pop();
            if (vis[v]) continue;
            vis[v] = 1;

            wolf.push_back(v);

            for (int i: graph[v]) {
                if (vis[i]) continue;
                pq.push(i);
            }
        }
    }

    {
        priority_queue<int> pq;
        pq.push(N-1);

        vector<bool> vis(N);

        while (pq.size()) {
            int v = pq.top();
            pq.pop();
            if (vis[v]) continue;
            vis[v] = 1;

            human.push_back(v);

            for (int i: graph[v]) {
                if (vis[i]) continue;
                pq.push(i);
            }
        }
    }

    assert((int)human.size() == N && (int)wolf.size() == N);
}

vector<int> wolfInv, humanInv, humanToWolf;

void makeInv() {
    wolfInv.resize(N);
    humanInv.resize(N);
    for (int i = 0; i<N; i++) wolfInv[wolf[i]] = i;
    for (int i = 0; i<N; i++) humanInv[human[i]] = i;

    humanToWolf.resize(N);
    for (int i = 0; i<N; i++) humanToWolf[i] = wolfInv[human[i]];
}


struct seg {
    struct node {
        int val=0, left=-1, right=-1;
    };

    vector<node> tree = {node()};

    void build(int v, int rl, int rr) {
        if (rl == rr) return;

        tree[v].left = tree.size();
        tree.push_back(node());
        tree[v].right = tree.size();
        tree.push_back(node());

        int rm = (rl + rr)/2;

        build(tree[v].left, rl, rm);
        build(tree[v].right, rm+1, rr);
    }

    int update(int v, int rl, int rr, int pos, int x) {
        if (rl == rr) {
            int newV = tree.size();
            tree.push_back(tree[v]);

            tree[newV].val += x;
            return newV;
        }
        int rm = (rl + rr)/2;

        int newV = tree.size();
        tree.push_back(tree[v]);

        if (pos <= rm) tree[newV].left = update(tree[newV].left, rl, rm, pos, x);
        else tree[newV].right = update(tree[newV].right, rm+1, rr, pos, x);

        tree[newV].val = tree[tree[newV].left].val + tree[tree[newV].right].val;

        return newV;
    }

    int query(int v, int rl, int rr, int ql, int qr) {
        if (ql > qr) return 0;
        if (rl == ql && rr == qr) return tree[v].val;

        int rm = (rl + rr)/2;

        return query(tree[v].left, rl, rm, ql, min(qr, rm)) + query(tree[v].right, rm+1, rr, max(ql, rm+1), qr);
    }

    vector<int> times;

    int queryDouble(int hl, int hr, int wl, int wr) {
        // cerr << query(times[wr], 0, N-1, hl, hr) << " - " << query(times[wl-1], 0, N-1, hl, hr) << "\n";
        // return query(times[wr], 0, N-1, hl, hr) - (wl==0?0:query(times[wl-1], 0, N-1, hl, hr));
        return query(times[hr], 0, N-1, wl, wr) - (hl==0?0:query(times[hl-1], 0, N-1, wl, wr));
    }

    void init() {
        build(0, 0, N-1);
        for (int i = 0; i<N; i++) {
            times.push_back(update(i==0?0:times.back(), 0, N-1, humanToWolf[i], 1));
        }
        assert((int)times.size() == N);
    }
};

struct segSimple {
    vector<pair<int, int>> tree;

    pair<int, int> op(pair<int, int> a, pair<int, int> b) {
        pair<int, int> res;
        res.first = min(a.first, b.first);
        res.second = max(a.second, b.second);

        return res;
    }

    void update(int v, int rl, int rr, int pos, int x) {
        if (rl == rr) {
            tree[v] = {x, x};
            return;
        }
        int rm = (rl + rr)/2;
        if (pos <= rm) update(v*2, rl, rm, pos, x);
        else update(v*2+1, rm+1, rr, pos, x);
        tree[v] = op(tree[v*2], tree[v*2+1]);
    }

    pair<int, int> query(int v, int rl, int rr, int ql, int qr) {
        if (ql > qr) return {1e9, -1e9};
        if (ql == rl && qr == rr) return tree[v];

        int rm = (rl + rr) / 2;

        return op(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr));
    }

    void init(vector<int> a) {
        tree.assign(N*4, {1e9, -1e9});

        for (int i = 0; i<N; i++) {
            update(1, 0, N-1, i, a[i]);
        }
    }
};


pair<int, int> getRangeHuman(segSimple s, int pos, int lim) {
    pair<int, int> range;
    {
        int l = 0, r = pos;

        while (l < r) {
            int m = (l + r)/2;
            if (s.query(1, 0, N-1, m, pos).first >= lim) r = m;
            else l = m+1;
        }
        range.first = l;
    }
    {
        int l = pos, r = N-1;

        while (l < r) {
            int m = (l + r + 1)/2;
            if (s.query(1, 0, N-1, pos, m).first >= lim) l = m;
            else r = m-1;
        }
        range.second = l;
    }
    return range;
}

pair<int, int> getRangeWolf(segSimple s, int pos, int lim) {
    pair<int, int> range;
    {
        int l = 0, r = pos;

        while (l < r) {
            int m = (l + r)/2;
            if (s.query(1, 0, N-1, m, pos).second <= lim) r = m;
            else l = m+1;
        }
        range.first = l;
    }
    {
        int l = pos, r = N-1;

        while (l < r) {
            int m = (l + r + 1)/2;
            if (s.query(1, 0, N-1, pos, m).second <= lim) l = m;
            else r = m-1;
        }
        range.second = l;
    }
    return range;
}


vector<int> check_validity(int _N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    N = _N;
    M = X.size();
    Q = S.size();

    graph.clear();
    graph.resize(N);
    for (int i = 0; i<M; i++) {
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }

    makeArrays();
    makeInv();

    // for (int i: human) cerr << i << " ";
    // cerr << "\n";
    // for (int i: wolf) cerr << i << " ";
    // cerr << "\n";
    // for (int i: humanToWolf) cerr << i << " ";
    // cerr << "\n";

    seg tree;

    tree.init();

    segSimple humanSeg;
    humanSeg.init(human);
    segSimple wolfSeg;
    wolfSeg.init(wolf);

    vector<int> res(Q, 0);

    for (int i = 0; i<Q; i++) {
        // cerr << humanInv[S[i]] << "\n";
        pair<int, int> rangeHuman = getRangeHuman(humanSeg, humanInv[S[i]], L[i]);
        pair<int, int> rangeWolf = getRangeWolf(wolfSeg, wolfInv[E[i]], R[i]);

        // cerr << rangeHuman.first << " " << rangeHuman.second << " " << rangeWolf.first << " " << rangeWolf.second << "\n";

        // cerr << tree.queryDouble(rangeHuman.first, rangeHuman.second, rangeWolf.first, rangeWolf.second) << "\n";

        if (tree.queryDouble(rangeHuman.first, rangeHuman.second, rangeWolf.first, rangeWolf.second)) res[i] = 1;
    }
    return res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4041 ms 93692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -