Submission #1261461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261461		patgra	Tourism (JOI23_tourism)	C++20	100 / 100	1062 ms	65536 KiB

tourism

//#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

#include <iostream>
#include <vector>
#include <unordered_set>
#include <stack>
#include <algorithm>
#include <cassert>

int n, M, q;
vector<vector<int>> g0, spotsIn;
vector<vector<pair<int, int>>> st, g;
vector<int> spots, inPre, inPost, dep, inEu, answers;
vector<pair<pair<int, int>, int>> events;
int maxLog;
int pret, postt;
int tB;
vector<int> t;

void tAdd(int l, int r, int x) {
    if(l > r) return;
    l += tB, r += tB;
    t[l] += x;
    if(l != r) t[r] += x;
    while(l / 2 != r / 2) {
        if(l % 2 == 0) t[l + 1] += x;
        if(r % 2 == 1) t[r - 1] += x;
        l /= 2; r /= 2;
    }
}

int tSum(int i) {
    i += tB;
    auto ans = 0;
    while(i) ans += t[i], i /= 2;
    return ans;
}

void dfs(int v, int p) {
    dep[v] = dep[p] + 1;
    inPre[v] = pret++;
    inEu[v] = (int)st[0].size();
    st[0].pb({dep[v], v});
    repIn(u, g0[v]) if(u != p) dfs(u, v), st[0].pb({dep[v], v});
    inPost[v] = postt++;
}

int lca(int x, int y) {
    x = inEu[x]; y = inEu[y];
    int k = 31 - __builtin_clz(y - x + 1);
    return min(st[k][x], st[k][y - (1 << k) + 1]).second;
}

bool inSub(int v, int u) {
    return inPre[v] <= inPre[u] && inPost[u] <= inPost[v];
}

bool cmp(int x, int y) {
    return inPre[x] < inPre[y];
}

void makeG(vector<int>& inc) {
    DC << "Virtual tree of ";
    DEBUG repIn(i, inc) DC << i << ' ';
    DC << eol;
    ranges::sort(inc, cmp);
    unordered_set<int> inc2;
    int pr = 1;
    repIn(i, inc) inc2.insert(lca(pr, i)), pr = i, inc2.insert(i);
    inc.clear();
    repIn(i, inc2) inc.pb(i);
    ranges::sort(inc, cmp);
    stack<int> stk;
    repIn(i, inc) g[i].clear();
    repIn(i, inc) {
        while(!stk.empty() && !inSub(stk.top(), i)) stk.pop();
        if(!stk.empty()) {
            int c = abs(dep[i] - dep[stk.top()]);
            g[i].pb({stk.top(), c});
            g[stk.top()].pb({i, c});
            DC << ' ' << i << ' ' << stk.top() << ' ' << c << eol;
        }
        stk.push(i);
    }
    DC << eol;
}

pair<int, int> dfs2(int v, int p, int l, int r) {
    int mxl = -1, mnr = M + 1;
    auto tmp1 = ranges::lower_bound(spotsIn[v], (l + r) / 2);
    if(tmp1 != spotsIn[v].end()) {
        mnr = min(mnr, *tmp1);
        if(*tmp1 == (l + r) / 2) mxl = max(mxl, *tmp1);
    }
    if(tmp1 != spotsIn[v].begin()) {
        tmp1--;
        mxl = max(mxl, *tmp1);
    }
    repIn2(u, c, g[v]) if(u != p) {
        auto [x, y] = dfs2(u, v, l, r);
        DC << ' ' << v << ' ' << u << ' ' << c << " doesnt work in " << x << ' ' << y << eol;
        events.pb({{x, y}, c});
        mxl = max(mxl, x);
        mnr = min(mnr, y);
    }
    return {mxl, mnr};
}

void dq(int l, int r, vector<pair<pair<int, int>, int>> queries) {
    if(l > r) return;
    int m = (l + r) / 2;

    DC << "dq(" << l << ' ' << r << ") cuts at " << m << eol;
    events.clear();
    vector<int> inc;
    rep(i, l, r + 1) inc.pb(spots[i]);
    makeG(inc);
    dfs2(spots[m], 0, l, r);
    ranges::sort(events);
    ranges::sort(queries);
    int sm = 0;
    repIn2(ab, c, events) sm += c;
    DC << "tSet(" << m << ' ' << r << ' ' << sm << ")\n";
    rep(i, m, r + 1) tAdd(i, i, sm-tSum(i));
    int ei = 0;
    repIn2(ab, qi, queries) {
        auto [a, b] = ab;
        if(a > m || b < m) continue;
        while(ei < (int)events.size() && events[ei].first.first < a) {
            DC << "tAdd(" << m << ' ' << events[ei].first.second - 1 << ' ' << -events[ei].second << ")\n";
            tAdd(m, events[ei].first.second - 1, -events[ei].second), ei++;
        }
        DC << "answers[" << qi << "] = tSum(" << b << ") = " << tSum(b) << eol;
        answers[qi] = tSum(b);
    }

    vector<pair<pair<int, int>, int>> ql, qr;
    repIn2(ab, qi, queries) if(ab.second < m || ab.first > m) (ab.second < m ? ql : qr).pb({ab, qi});
    dq(l, m - 1, ql);
    dq(m + 1, r, qr);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> M >> q;
    int x, y;
    g0.resize(n + 1);
    spotsIn.resize(n + 1);
    st.resize(maxLog = 34 - __builtin_clz(n + 1));
    g.resize(n + 1);
    spots.resize(M);
    inPre.resize(n + 1);
    inPost.resize(n + 1);
    dep.resize(n + 1);
    inEu.resize(n + 1);
    answers.resize(q);
    t.resize(2 * (tB = 1 << (32 - __builtin_clz(M))));
    rep(i, 1, n) {
        cin >> x >> y;
        g0[x].pb(y);
        g0[y].pb(x);
    }

    dfs(1, 0);
    rep(k, 1, maxLog) rep(i, 0, (int)st[0].size()) st[k].pb(min(st[k - 1][i], st[k - 1][min((int)st[0].size() - 1, i + (1 << (k - 1)))]));

    if(0) DEBUG {
        rep(i, 0, 1 << n) {
            DC << "Virtual tree of ";
            vector<int> inc;
            rep(j, 0, n) if(i & (1 << j)) {
                DC << j + 1 << ' ';
                inc.pb(j + 1);
            }
            DC << eol;
            makeG(inc);
            repIn(j, inc) repIn2(u, c, g[j]) if(j < u) DC << ' ' << u << ' ' << j << ' ' << c << eol;
            DC << eol;
        }
    }

    rep(i, 0, M) cin >> spots[i], spotsIn[spots[i]].pb(i);
    rep(i, 1, n + 1) ranges::sort(spotsIn[i]);

    vector<pair<pair<int, int>, int>> queries(q);
    rep(i, 0, q) {
        int a, b;
        cin >> a >> b;
        a--;b--;
        queries[i] = {{a, b}, i};
    }

    dq(0, M - 1, queries);
    repIn(i, answers) cout << i + 1 << '\n';
}

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