oj.uz

Submission #789188

# Submission time Handle Problem Language Result Execution time Memory
789188 2023-07-21T07:15:08 Z 이성호(#10043) Tourism (JOI23_tourism) C++17
28 / 100
 5000 ms 571164 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;
int c[100005], verc[100005], ans[100005], res[100005], ver[100005];
int N, K, M, Q, pv = 0;
vector<int> adj[100005];
const int inf = 1e9;
pair<int, int> ett[100005]; //(first, second)
vector<int> dot[300005];
struct Query
{
    int sgn;
    int id;
    int y;
};
struct Calc
{
    int id;
    int l, r;
    bool operator<(const Calc &c)
    {
        if (l / K == c.l / K) return r < c.r;
        else return l < c.l;
    }
};
Calc qr[100005];
vector<Query> query[300005];
void add_query(int sgn, int x1, int x2, int y1, int y2, int id)
{
    Query q1, q2, q3, q4;
    q1 = {sgn, id, y2};
    q2 = {-sgn, id, y2};
    q3 = {-sgn, id, y1-1};
    q4 = {sgn, id, y1-1};
    query[x2].push_back(q1); query[x2].push_back(q3);
    query[x1-1].push_back(q2); query[x1-1].push_back(q4);
}
struct FenWick
{
    vector<int> tree;
    int n;
    FenWick(int N)
    {
        n = N;
        tree.resize(N+1);
    }
    void upd(int i, int x)
    {
        for (; i <= n; i += i&-i) tree[i] += x;
    }
    int query(int i)
    {
        int ret = 0;
        for (; i; ret += tree[i], i -= i&-i);
        return ret;
    }
};
void dfs(int v, int p)
{
    if (p) ett[v].first = ++pv;
    ver[v] = ++pv;
    for (int i:adj[v]) {
        if (i != p) {
            dfs(i, v);
        }
    }
    if (p) ett[v].second = ++pv;
}
multiset<int> curver;
void add(int id, int c)
{
    if (curver.empty()) {
        curver.insert(c);
        return;
    }
    auto it = curver.lower_bound(c);
    if (it == curver.end()) {
        int s = *curver.begin(), e = *--curver.end();
        add_query(1, 1, s, e, c-1, id);
    }
    else if (it == curver.begin()) {
        int s = *it, e = *--curver.end();
        add_query(1, c+1, s, e, pv, id);
    }
    int bef;
    if (it == curver.begin()) bef = 1;
    else {
        bef = *--it + 1; ++it;
    }
    int aft;
    if (it == curver.end()) aft = pv;
    else aft = *it - 1;
    add_query(1, bef, c, c, aft, id);
    curver.insert(c);
}
void del(int id, int c)
{
    curver.erase(curver.find(c));
    if (curver.empty()) return;
    auto it = curver.lower_bound(c);
    if (it == curver.end()) {
        int s = *curver.begin(), e = *--curver.end();
        add_query(-1, 1, s, e, c-1, id);
    }
    else if (it == curver.begin()) {
        int s = *it, e = *--curver.end();
        add_query(-1, c+1, s, e, pv, id);
    }
    int bef;
    if (it == curver.begin()) bef = 1;
    else {
        bef = *--it + 1; ++it;
    }
    int aft;
    if (it == curver.end()) aft = pv;
    else aft = *it - 1;
    add_query(-1, bef, c, c, aft, id);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> M >> Q;
    K = sqrt(N);
    for (int i = 1; i < N; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 2; i <= N; i++) dot[ett[i].first].push_back(ett[i].second);
    for (int i = 1; i <= M; i++) {
        cin >> c[i];
        verc[i] = ver[c[i]];
    }
    for (int i = 1; i <= Q; i++) {
        cin >> qr[i].l >> qr[i].r;
        qr[i].id = i;
    }
    sort(qr + 1, qr + Q + 1);
    int nl = 1, nr = 0;
    for (int i = 1; i <= Q; i++) {
        while (nr < qr[i].r) add(i, verc[++nr]);
        while (nl > qr[i].l) add(i, verc[--nl]);
        while (nr > qr[i].r) del(i, verc[nr--]);
        while (nl < qr[i].l) del(i, verc[nl++]);
    }
    FenWick fenWick(pv);
    for (int i = 1; i <= pv; i++) {
        for (int j:dot[i]) {
            fenWick.upd(j, 1);
        }
        for (Query j:query[i]) {
            int tmp = fenWick.query(j.y);
            if (j.sgn == 1) ans[j.id] += tmp;
            else ans[j.id] -= tmp;
        }
    }
    for (int i = 1; i <= Q; i++) ans[i] += ans[i-1];
    for (int i = 1; i <= Q; i++) res[qr[i].id] = ans[i];
    for (int i = 1; i <= Q; i++) cout << res[i] + 1 << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Correct 9 ms 16804 KB Output is correct
4 Correct 9 ms 17128 KB Output is correct
5 Correct 9 ms 16980 KB Output is correct
6 Correct 9 ms 17108 KB Output is correct
7 Correct 9 ms 16996 KB Output is correct
8 Correct 9 ms 16980 KB Output is correct
9 Correct 10 ms 17236 KB Output is correct
10 Correct 9 ms 17316 KB Output is correct
11 Correct 11 ms 17236 KB Output is correct
12 Correct 9 ms 16852 KB Output is correct
13 Correct 9 ms 16968 KB Output is correct
14 Correct 11 ms 16852 KB Output is correct
15 Correct 10 ms 17308 KB Output is correct
16 Correct 10 ms 17236 KB Output is correct
17 Correct 11 ms 17364 KB Output is correct
18 Correct 10 ms 17236 KB Output is correct
19 Correct 9 ms 17292 KB Output is correct
20 Correct 12 ms 17300 KB Output is correct
21 Correct 10 ms 17256 KB Output is correct
22 Correct 9 ms 17236 KB Output is correct
23 Correct 9 ms 17288 KB Output is correct
24 Correct 10 ms 17364 KB Output is correct
25 Correct 9 ms 17236 KB Output is correct
26 Correct 9 ms 17236 KB Output is correct
27 Correct 11 ms 19368 KB Output is correct
28 Correct 8 ms 16724 KB Output is correct
29 Correct 8 ms 16768 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Correct 9 ms 16804 KB Output is correct
4 Correct 9 ms 17128 KB Output is correct
5 Correct 9 ms 16980 KB Output is correct
6 Correct 9 ms 17108 KB Output is correct
7 Correct 9 ms 16996 KB Output is correct
8 Correct 9 ms 16980 KB Output is correct
9 Correct 10 ms 17236 KB Output is correct
10 Correct 9 ms 17316 KB Output is correct
11 Correct 11 ms 17236 KB Output is correct
12 Correct 9 ms 16852 KB Output is correct
13 Correct 9 ms 16968 KB Output is correct
14 Correct 11 ms 16852 KB Output is correct
15 Correct 10 ms 17308 KB Output is correct
16 Correct 10 ms 17236 KB Output is correct
17 Correct 11 ms 17364 KB Output is correct
18 Correct 10 ms 17236 KB Output is correct
19 Correct 9 ms 17292 KB Output is correct
20 Correct 12 ms 17300 KB Output is correct
21 Correct 10 ms 17256 KB Output is correct
22 Correct 9 ms 17236 KB Output is correct
23 Correct 9 ms 17288 KB Output is correct
24 Correct 10 ms 17364 KB Output is correct
25 Correct 9 ms 17236 KB Output is correct
26 Correct 9 ms 17236 KB Output is correct
27 Correct 11 ms 19368 KB Output is correct
28 Correct 8 ms 16724 KB Output is correct
29 Correct 8 ms 16768 KB Output is correct
30 Correct 24 ms 21844 KB Output is correct
31 Correct 29 ms 22960 KB Output is correct
32 Correct 43 ms 25080 KB Output is correct
33 Correct 39 ms 25192 KB Output is correct
34 Correct 35 ms 25284 KB Output is correct
35 Correct 13 ms 18656 KB Output is correct
36 Correct 13 ms 18772 KB Output is correct
37 Correct 16 ms 18744 KB Output is correct
38 Correct 39 ms 25128 KB Output is correct
39 Correct 36 ms 25224 KB Output is correct
40 Correct 37 ms 25332 KB Output is correct
41 Correct 13 ms 18760 KB Output is correct
42 Correct 13 ms 18772 KB Output is correct
43 Correct 14 ms 18644 KB Output is correct
44 Correct 35 ms 25444 KB Output is correct
45 Correct 36 ms 25340 KB Output is correct
46 Correct 40 ms 25308 KB Output is correct
47 Correct 13 ms 18824 KB Output is correct
48 Correct 13 ms 18644 KB Output is correct
49 Correct 16 ms 18752 KB Output is correct
50 Correct 43 ms 25296 KB Output is correct
51 Correct 42 ms 25160 KB Output is correct
52 Correct 36 ms 25284 KB Output is correct
53 Correct 37 ms 25420 KB Output is correct
54 Correct 41 ms 25080 KB Output is correct
55 Correct 38 ms 25292 KB Output is correct
56 Correct 160 ms 156284 KB Output is correct
57 Correct 9 ms 16980 KB Output is correct
58 Correct 10 ms 17408 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 11 ms 19360 KB Output is correct
3 Correct 151 ms 156304 KB Output is correct
4 Execution timed out 5099 ms 571164 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 76 ms 29736 KB Output is correct
3 Correct 109 ms 35276 KB Output is correct
4 Correct 111 ms 32732 KB Output is correct
5 Correct 158 ms 38024 KB Output is correct
6 Correct 226 ms 40792 KB Output is correct
7 Correct 207 ms 40404 KB Output is correct
8 Correct 208 ms 40084 KB Output is correct
9 Correct 190 ms 39980 KB Output is correct
10 Correct 162 ms 39944 KB Output is correct
11 Correct 152 ms 40076 KB Output is correct
12 Correct 140 ms 40508 KB Output is correct
13 Correct 151 ms 41804 KB Output is correct
14 Correct 152 ms 45136 KB Output is correct
15 Correct 174 ms 51520 KB Output is correct
16 Correct 185 ms 42600 KB Output is correct
17 Correct 182 ms 42544 KB Output is correct
18 Correct 176 ms 42488 KB Output is correct
19 Correct 157 ms 38048 KB Output is correct
20 Correct 181 ms 40852 KB Output is correct
21 Correct 188 ms 40620 KB Output is correct
22 Correct 173 ms 40440 KB Output is correct
23 Correct 200 ms 40280 KB Output is correct
24 Correct 168 ms 40140 KB Output is correct
25 Correct 161 ms 40004 KB Output is correct
26 Correct 172 ms 40096 KB Output is correct
27 Correct 140 ms 40016 KB Output is correct
28 Correct 135 ms 40088 KB Output is correct
29 Correct 142 ms 40268 KB Output is correct
30 Correct 146 ms 40852 KB Output is correct
31 Correct 134 ms 41832 KB Output is correct
32 Correct 143 ms 43524 KB Output is correct
33 Correct 157 ms 47848 KB Output is correct
34 Correct 166 ms 51540 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16704 KB Output is correct
2 Correct 12 ms 19316 KB Output is correct
3 Correct 164 ms 156384 KB Output is correct
4 Execution timed out 5041 ms 502420 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Correct 9 ms 16804 KB Output is correct
4 Correct 9 ms 17128 KB Output is correct
5 Correct 9 ms 16980 KB Output is correct
6 Correct 9 ms 17108 KB Output is correct
7 Correct 9 ms 16996 KB Output is correct
8 Correct 9 ms 16980 KB Output is correct
9 Correct 10 ms 17236 KB Output is correct
10 Correct 9 ms 17316 KB Output is correct
11 Correct 11 ms 17236 KB Output is correct
12 Correct 9 ms 16852 KB Output is correct
13 Correct 9 ms 16968 KB Output is correct
14 Correct 11 ms 16852 KB Output is correct
15 Correct 10 ms 17308 KB Output is correct
16 Correct 10 ms 17236 KB Output is correct
17 Correct 11 ms 17364 KB Output is correct
18 Correct 10 ms 17236 KB Output is correct
19 Correct 9 ms 17292 KB Output is correct
20 Correct 12 ms 17300 KB Output is correct
21 Correct 10 ms 17256 KB Output is correct
22 Correct 9 ms 17236 KB Output is correct
23 Correct 9 ms 17288 KB Output is correct
24 Correct 10 ms 17364 KB Output is correct
25 Correct 9 ms 17236 KB Output is correct
26 Correct 9 ms 17236 KB Output is correct
27 Correct 11 ms 19368 KB Output is correct
28 Correct 8 ms 16724 KB Output is correct
29 Correct 8 ms 16768 KB Output is correct
30 Correct 24 ms 21844 KB Output is correct
31 Correct 29 ms 22960 KB Output is correct
32 Correct 43 ms 25080 KB Output is correct
33 Correct 39 ms 25192 KB Output is correct
34 Correct 35 ms 25284 KB Output is correct
35 Correct 13 ms 18656 KB Output is correct
36 Correct 13 ms 18772 KB Output is correct
37 Correct 16 ms 18744 KB Output is correct
38 Correct 39 ms 25128 KB Output is correct
39 Correct 36 ms 25224 KB Output is correct
40 Correct 37 ms 25332 KB Output is correct
41 Correct 13 ms 18760 KB Output is correct
42 Correct 13 ms 18772 KB Output is correct
43 Correct 14 ms 18644 KB Output is correct
44 Correct 35 ms 25444 KB Output is correct
45 Correct 36 ms 25340 KB Output is correct
46 Correct 40 ms 25308 KB Output is correct
47 Correct 13 ms 18824 KB Output is correct
48 Correct 13 ms 18644 KB Output is correct
49 Correct 16 ms 18752 KB Output is correct
50 Correct 43 ms 25296 KB Output is correct
51 Correct 42 ms 25160 KB Output is correct
52 Correct 36 ms 25284 KB Output is correct
53 Correct 37 ms 25420 KB Output is correct
54 Correct 41 ms 25080 KB Output is correct
55 Correct 38 ms 25292 KB Output is correct
56 Correct 160 ms 156284 KB Output is correct
57 Correct 9 ms 16980 KB Output is correct
58 Correct 10 ms 17408 KB Output is correct
59 Correct 9 ms 16724 KB Output is correct
60 Correct 11 ms 19360 KB Output is correct
61 Correct 151 ms 156304 KB Output is correct
62 Execution timed out 5099 ms 571164 KB Time limit exceeded
63 Halted 0 ms 0 KB -