oj.uz

Submission #746341

# Submission time Handle Problem Language Result Execution time Memory
746341 2023-05-22T11:31:30 Z baluteshih Tourism (JOI23_tourism) C++14
0 / 100
 136 ms 22396 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

const int MAXN = 100005;
const int K = 320;

struct Node {
    int mi, micnt, smi, lazy;
} seg[MAXN << 2];

int cnt[MAXN], bcnt[MAXN / K + 1];

void up(int rt) {
    seg[rt].mi = min(seg[rt << 1].mi, seg[rt << 1 | 1].mi);
    seg[rt].micnt = 0;
    seg[rt].smi = min(seg[rt << 1].smi, seg[rt << 1 | 1].smi);
    if (seg[rt].mi == seg[rt << 1].mi) seg[rt].micnt += seg[rt << 1].micnt;
    else seg[rt].smi = min(seg[rt].smi, seg[rt << 1].mi);
    if (seg[rt].mi == seg[rt << 1 | 1].mi) seg[rt].micnt += seg[rt << 1 | 1].micnt;
    else seg[rt].smi = min(seg[rt].smi, seg[rt << 1 | 1].mi);
}

void build(int l, int r, int rt) {
    if (l == r) {
        seg[rt].mi = 0;
        seg[rt].micnt = 1;
        seg[rt].smi = MAXN;
        seg[rt].lazy = -1;
        ++cnt[0], ++bcnt[0];
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);
    up(rt);
}

void give_tag(int rt, int v, int mdfy = 0) {
    if (mdfy) {
        //cerr << "remove " << seg[rt].mi << " " << seg[rt].micnt << "\n";
        cnt[seg[rt].mi] -= seg[rt].micnt;
        bcnt[seg[rt].mi / K] -= seg[rt].micnt;
    }
    seg[rt].mi = max(seg[rt].mi, v);
    seg[rt].lazy = max(seg[rt].lazy, v);
    if (mdfy) {
        //cerr << "add " << seg[rt].mi << " " << seg[rt].micnt << "\n";
        cnt[seg[rt].mi] += seg[rt].micnt;
        bcnt[seg[rt].mi / K] += seg[rt].micnt;
    }
}

void down(int rt) {
    if (seg[rt].lazy != -1) {
        give_tag(rt << 1, seg[rt].lazy);
        give_tag(rt << 1 | 1, seg[rt].lazy);
        seg[rt].lazy = -1;
    }
}

void modify(int L, int R, int l, int r, int rt, int v) {
    if (v <= seg[rt].mi) return;
    if (L <= l && R >= r && v < seg[rt].smi)
        return give_tag(rt, v, 1);
    down(rt);
    int mid = (l + r) >> 1;
    if (L <= mid) modify(L, R, l, mid, rt << 1, v);
    if (R > mid) modify(L, R, mid + 1, r, rt << 1 | 1, v);
    up(rt);
}

int query(int l) {
    int ans = 0;
    for (int i = 0; (i + 1) * K <= l; ++i)
        ans += bcnt[i];
    for (int i = l / K * K; i < l; ++i)
        ans += cnt[i];
    return ans;
}

struct Heavy_light_Decomposition { // 1-base
    int n, ulink[MAXN], deep[MAXN], mxson[MAXN], w[MAXN], pa[MAXN];
    int t, seq[MAXN], pl[MAXN], out[MAXN];
    vector<int> G[MAXN];
    void init(int _n) {
        n = _n, t = 0;
        for (int i = 1; i <= n; ++i)
            G[i].clear(), mxson[i] = 0;
    }
    void add_edge(int a, int b) {
        G[a].pb(b);
        G[b].pb(a);
    }
    void dfs(int u, int f, int d) {
        w[u] = 1, pa[u] = f, deep[u] = d++;
        for (auto i : G[u])
            if (i != f) {
                dfs(i, u, d), w[u] += w[i];
                if (w[mxson[u]] < w[i]) mxson[u] = i;
            } 
    }
    void cut(int u, int link) {
        seq[pl[u] = ++t] = u, ulink[u] = link;
        if (mxson[u]) {
            cut(mxson[u], link);
            for (auto i : G[u])
                if (i != pa[u] && i != mxson[u])
                    cut(i, i);
        }
        out[u] = t;
    }
    void solve() { 
        dfs(1, 0, 1);
        cut(1, 1);
        build(1, t, 1);
    }
    void mdfy(int a, int v) {
        while (a) {
            int ta = ulink[a];
            //cerr << "mdfy " << "[" << pl[ta] << ", " << pl[a] << "] " << v << endl; 
            modify(pl[ta], pl[a], 1, n, 1, v);
            a = pa[ta];
        }
    }
} hld;

int arr[MAXN], ans[MAXN];
int mi[__lg(MAXN) + 1][MAXN], mx[__lg(MAXN) + 1][MAXN];
int bit[MAXN], bit_all;
vector<pii> qry[MAXN], full[MAXN];

int get_mi(int l, int r) {
    int lg = __lg(r - l + 1);
    return min(mi[lg][l], mi[lg][r - (1 << lg) + 1]);
}

int get_mx(int l, int r) {
    int lg = __lg(r - l + 1);
    return max(mx[lg][l], mx[lg][r - (1 << lg) + 1]);
}

void bit_modify(int x, int v) {
    for (bit_all += v; x <= hld.t; x += x & -x)
        bit[x] += v;
}

int bit_query(int x) {
    int res = 0;
    for (; x; x -= x & -x)
        res += bit[x];
    return res;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    hld.init(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        hld.add_edge(u, v);
    }
    hld.solve();
    for (int i = 1; i <= m; ++i)
        cin >> arr[i];
    for (int i = 1; i <= m; ++i)
        mi[0][i] = mx[0][i] = hld.pl[arr[i]];  
    int L = __lg(m);
    for (int i = 1; i <= L; ++i)
        for (int j = 1; j + (1 << i) <= n + 1; ++j) {
            mi[i][j] = min(mi[i - 1][j], mi[i - 1][j + (1 << (i - 1))]);
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
        }
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        qry[r].pb(pii(l, i));
        int a = get_mi(l, r);
        int b = get_mx(l, r);
        full[a].pb(pii(b, i));
        ans[i] = n + 1;
    }

    /*for (int i = 1; i <= n; ++i)
        cerr << hld.seq[i] << " ";
    cerr << endl;*/

    // full
    for (int i = 1; i <= n; ++i) {
        bit_modify(hld.out[hld.seq[i]], 1);
        for (auto [r, idx] : full[i])
            ans[idx] -= bit_all - bit_query(r - 1);
    }

    /*for (int i = 1; i <= q; ++i)
        cerr << ans[i] << " ";
    cerr << endl;*/

    // zero
    for (int i = 1; i <= n; ++i) {
        hld.mdfy(arr[i], i);
        //cerr << i << " done\n";
        for (auto [l, idx] : qry[i])
            ans[idx] -= query(l);
    }

    for (int i = 1; i <= q; ++i)
        cout << ans[i] << "\n";
}

Compilation message

tourism.cpp: In function 'int main()':
tourism.cpp:199:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  199 |         for (auto [r, idx] : full[i])
      |                   ^
tourism.cpp:211:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  211 |         for (auto [l, idx] : qry[i])
      |                   ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7364 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Incorrect 4 ms 7508 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7364 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Incorrect 4 ms 7508 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 114 ms 20940 KB Output is correct
3 Incorrect 136 ms 22396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7364 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Incorrect 4 ms 7508 KB Output isn't correct
5 Halted 0 ms 0 KB -