Submission #796482

#	Time	Username	Problem	Language	Result	Execution time	Memory
796482		Johann	Tourism (JOI23_tourism)	C++14	24 / 100	1271 ms	12664 KiB

tourism

#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef tuple<int, int, int> tiii;
typedef vector<tiii> vtiii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, M, Q;
vi C;
vvi adj;
vi cnt;
struct query
{
    int l, r, idx;
};
vector<query> queries;
int ans;
vi answers;

struct segtree
{
    vi arr;
    int size;
    int NEUTRAL = 0;
    int merge(int a, int b)
    {
        if (a == NEUTRAL || b == NEUTRAL)
            return max(a, b);
        while (a != b)
        {
            if (a < b)
                swap(a, b);
            a >>= 1;
        }
        return a;
    }
    void init(vi &A)
    {
        size = 1;
        while (size < sz(A))
            size *= 2;
        arr.assign(2 * size, NEUTRAL);

        for (int i = 0; i < sz(A); ++i)
            arr[i + size] = A[i];
        for (int i = size - 1; i > 0; --i)
            arr[i] = merge(arr[2 * i], arr[2 * i + 1]);
    }
    int query(int l, int r) { return query(l, r, 1, 0, size); }
    int query(int l, int r, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
            return arr[x];
        if (r <= lx || rx <= l)
            return NEUTRAL;
        int m = (lx + rx) / 2;
        return merge(query(l, r, 2 * x, lx, m), query(l, r, 2 * x + 1, m, rx));
    }
};
segtree seglca;

void add(int x)
{
    while (x > 0)
    {
        ++cnt[x];
        if (cnt[x] == 1)
            ++ans;
        x >>= 1;
    }
}
void sub(int x)
{
    while (x > 0)
    {
        --cnt[x];
        if (cnt[x] == 0)
            --ans;
        x >>= 1;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M >> Q;

    adj.resize(N);
    for (int i = 0, a, b; i < N - 1; ++i)
    {
        cin >> a >> b;
        --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }

    C.resize(M);
    for (int i = 0; i < M; ++i)
    {
        cin >> C[i];
        // --C[i]; not for binary tree!
    }
    seglca.init(C);

    int sq = 1;
    while (sq * sq < M)
        ++sq;
    queries.resize(Q);
    answers.resize(Q);
    for (int i = 0, l, r; i < Q; ++i)
    {
        cin >> l >> r;
        --l;
        queries[i] = {l, r, i};
    }
    sort(all(queries), [&](const query &a, const query &b)
         { if (a.l / sq != b.l / sq) return a.l < b.l; else return a.r < b.r; });

    int lx = 0, rx = 0;
    ans = 0;
    cnt.assign(N + 1, 0);
    for (query q : queries)
    {
        while (rx < q.r)
            add(C[rx++]);
        while (lx > q.l)
            add(C[--lx]);
        while (rx > q.r)
            sub(C[--rx]);
        while (lx < q.l)
            sub(C[lx++]);

        int tmp = ans;
        int lca = seglca.query(q.l, q.r);
        lca >>= 1;
        while (lca > 0)
            --tmp, lca >>= 1;

        answers[q.idx] = tmp;
    }

    for (int x : answers)
        cout << x << "\n";
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 24 / 24
• Subtask 6: 0 / 41