Submission #950888

#	Time	Username	Problem	Language	Result	Execution time	Memory
950888		vjudge1	Tourism (JOI23_tourism)	C++17	0 / 100	608 ms	20464 KiB

tourism

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ld = long double;  // or double, if TL is tight
using str = string; 
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

struct AIB {
    int n;
    vi V;
    AIB(int N) : n(N + 1), V(N + 1) {}

    void update(int p, int v) {
        ++p;
        while(p < n) {
            V[p] += v;
            p += p & - p;
        }
    }

    int query(int p) {
        ++p;
        int re = 0;
        while(p) {
            re += V[p];
            p -= p & -p;
        }
        return re;
    }

    int query(int st, int dr) {
        return query(dr) - query(st - 1);
    }
};

struct Segmente {
    int n;
    set<pair<ii, int> > S;

    AIB Fr;

    Segmente(int N) : n(N), Fr(N + 1) {
        S.insert({ii{0, n - 1}, n + 1});
        Fr.update(n + 1, n);
    }

    void init() {

    }
    
    void update(int l, int r, int v) { /// l...r <- v
        if(l > r) return;
        auto primul = S.upper_bound({ii{l, 1e9}, 0});
        --primul;
        auto ultimul = S.lower_bound({ii{r + 1, -1e9}, 0});
        --ultimul;
        
        vector<pair<ii, int> > ToDelete;
        while(primul != ultimul) {
            ToDelete.push_back(*primul);
            ++primul;
        }
        ToDelete.push_back(*primul);

        auto sterge = [&](pair<ii, int> a) {
            S.erase(a);
            auto [st, dr] = a.first;
            int len = dr - st + 1;
            Fr.update(a.second, -len);
        };
        auto adauga = [&](int st, int dr, int v) {
            pair<ii, int> a = {ii{st, dr}, v};
            S.insert(a);
            int len = dr - st + 1;
            Fr.update(v, len);
        };

        for(auto it : ToDelete) sterge(it);
        
        auto minus = [&](ii seg1, ii seg2) -> vector<ii> {
            auto [s1, d1] = seg1;
            auto [s2, d2] = seg2;
            if(d1 < s2 || d2 < s1) return {seg1};
           // if(s2 <= s1 && d1 <= d2) return {};
           // if(s1 < s2 && d1 <= d2) return {ii{s1, s2 - 1}};
           // if(s2 <= s1 && d2 < d1) return {ii{d2 + 1, d1}};
            return {ii{s1, s2 - 1}, ii{d2 + 1, d1}};
        };
        auto len = [&](ii a) { return a.second - a.first + 1; };

        auto scrap = [&](auto x) {
            for(auto it : minus(x.first, ii{l, r}))
                if(len(it) > 0) adauga(it.first, it.second, x.second);
        };
        scrap(ToDelete[0]);
        if(ToDelete.size() > 1) scrap(ToDelete.back());

        adauga(l, r, v);
    }

    int query(int r) {
        return Fr.query(r);
    }
};

struct tree {
    int n, tmr = 0;
    vi par, niv, sz, nxt, in;
    vector<vi> L, G, Anc;

    Segmente A;

    tree(int N) : n(N), par(N), niv(N), sz(N, 0), 
    nxt(N, 0), in(N, 0), L(N), G(N), A(N) {} /// nxt[u] e capul la lant

    void add_edge(int u, int v) {
        L[u].push_back(v);
        L[v].push_back(u);
    }

    void init() {
        function<void(int, int, int)> dfs0 = [&](int u, int p, int li) {
            par[u] = p;
            niv[u] = li;
            sz[u] = 1;
            for (auto it : L[u])
                if (it != p) {
                    dfs0(it, u, li + 1);
                    sz[u] += it;
                    G[u].push_back(it);
                }
        };
        dfs0(0, -1, 0);

        A.init();

        function<void(int, int)> dfs1 = [&](int u, int p) {
            sort(all(G[u]), [&](auto a, auto b) { return sz[a] > sz[b]; });
            in[u] = tmr++;
            if (G[u].empty()) return;
            nxt[G[u][0]] = nxt[u];
            dfs1(G[u][0], u);
            for (int i = 1; i < G[u].size(); ++i) {
                nxt[G[u][i]] = G[u][i];
                dfs1(G[u][i], u);
            }
        };
        dfs1(0, -1);
        
        Anc.push_back(par);
        for (int k = 1; (1 << k) <= n; ++k) {
            Anc.push_back(vi(n, -1));
            for (int i = 0; i < n; ++i) {
                Anc[k][i] = Anc[k - 1][i] == -1 ? -1 : Anc[k - 1][Anc[k - 1][i]];
            }
        }
    }

    int lift(int u, int nr) {
        for (int i = 0; i < (int)Anc.size(); ++i)
            if (nr & (1 << i))
                u = Anc[i][u];
        return u;
    }

    int lca(int u, int v) {
        if(niv[u] > niv[v]) swap(u, v);
        v = lift(v, niv[v] - niv[u]);
        if(u == v) return u;
        for(int i = (int)Anc.size() - 1; i >= 0; --i)
            if(Anc[i][u] != Anc[i][v]) {
                u = Anc[i][u];
                v = Anc[i][v];
            }
        return par[u];
    }

    void update_lant(int l, int u, int val) { /// (l, u] update
        if(niv[l] == niv[u]) return;
        while(u != -1) {
            if(niv[nxt[u]] > niv[l]) {
                A.update(in[nxt[u]], in[u], val);
                u = par[nxt[u]];
            } else {
                A.update(in[l] + 1, in[u], val);
                break;
            }
        }
    }

    void update(int u, int v, int val) {
        int l = lca(u, v);
        update_lant(l, u, val);
        update_lant(l, v, val);
    }

    int query(int r) { /// nr chestii <= r
        return A.query(r);
    }
};

struct RMQ_LCA {
    int m;
    tree &T;
    vi C;
    vector<vi> Re;

    RMQ_LCA(int N, vi C0, tree &T0) : m(C0.size()), C(C0), T(T0) {
        Re.push_back(C);
        for(int k = 1; (1 << k) <= m; ++k) {
            Re.push_back(vi(m, 0));
            for(int i = 0; i < m; ++i) {
                if(i + (1 << (k - 1)) < m)
                    Re[k][i] = T.lca(Re[k - 1][i], Re[k - 1][i + (1 << (k - 1))]);
                else Re[k][i] = Re[k - 1][i];
            }
        }
    }

    int query(int st, int dr) {
        int l = 31 - __builtin_clz(dr - st + 1);
        return T.lca(Re[l][st], Re[l][dr - (1 << l) + 1]);
    }
};

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, m, q;
    cin >> n >> m >> q;
    tree T(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        T.add_edge(u, v);
    }
    T.init();
    vi C(m);
    for(int i = 0; i < m; ++i) {
        cin >> C[i];
        --C[i];
    }

    RMQ_LCA Stramos(n, C, T);

    int rad = (int)round(sqrt(double(n)));
    vector<pair<ii, int> > Q;
    vi Re(q, 0);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l; --r;
        Q.push_back({ii{l, r}, i});
    }
    sort(all(Q));

    int ult = C.back();
    int p = int(Q.size()) - 1;
    for(int i = m - 1; i >= 0; --i) {
        T.update(ult, C[i], i + 1);
        ult = C[i];
        while(p >= 0 && Q[p].first.first == i) {
            auto [seg, id] = Q[p];
            auto [l, r] = seg;
            Re[id] = T.query(r);
            --p;
        }
    }

    for(auto it : Re)
        cout << it + 1 << "\n";
    return 0;
}

Compilation message (stderr)

tourism.cpp: In lambda function:
tourism.cpp:152:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |             for (int i = 1; i < G[u].size(); ++i) {
      |                             ~~^~~~~~~~~~~~~
tourism.cpp: In constructor 'RMQ_LCA::RMQ_LCA(int, vi, tree&)':
tourism.cpp:214:8: warning: 'RMQ_LCA::C' will be initialized after [-Wreorder]
  214 |     vi C;
      |        ^
tourism.cpp:213:11: warning:   'tree& RMQ_LCA::T' [-Wreorder]
  213 |     tree &T;
      |           ^
tourism.cpp:217:5: warning:   when initialized here [-Wreorder]
  217 |     RMQ_LCA(int N, vi C0, tree &T0) : m(C0.size()), C(C0), T(T0) {
      |     ^~~~~~~
tourism.cpp: In function 'int main()':
tourism.cpp:256:9: warning: unused variable 'rad' [-Wunused-variable]
  256 |     int rad = (int)round(sqrt(double(n)));
      |         ^~~

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