oj.uz

Submission #898894

# Submission time Handle Problem Language Result Execution time Memory
898894 2024-01-05T08:50:24 Z Amirreza_Fakhri Regions (IOI09_regions) C++17
60 / 100
 6924 ms 131072 KB 
// In the name of the God 
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
 
const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e5+5, maxr = 25e3+5, sq = 334, sq_ = 600;
 
int n, q, t = 0, cur = 0, re[maxn], id[maxr], cnt[sq_], res[sq_][maxr], in[maxn], out[maxn];
vector <int> adj[maxn], oc[maxr], vec;
vector <pii> seg[maxn*4];
 
void dfs(int v = 0) {
    in[v] = t++; vec.pb(v);
    if (oc[re[v]].size() >= sq) cnt[id[re[v]]]++;
    for (int i = 0; i < sq_; i++) res[i][re[v]] += cnt[i];
    for (int u : adj[v]) dfs(u);
    if (oc[re[v]].size() >= sq) cnt[id[re[v]]]--;
    out[v] = t;
}
 
void build(int l = 0, int r = n, int id = 1) {
    if (l+1 == r) {
        seg[id].pb(mp(-1, 0));
        seg[id].pb(mp(re[vec[l]], 0));
        return;
    }
    int mid = (l+r)/2;
    build(l, mid, id*2), build(mid, r, id*2+1);
    int p1 = 1, p2 = 1;
    seg[id].pb(mp(-1, 0));
    while (p1 < mid-l+1 or p2 < r-mid+1) {
        if (p1 == mid-l+1) {
            seg[id].pb(mp(seg[id*2+1][p2].F, seg[id].back().S));
            p2++;
        }
        else if (p2 == r-mid+1) {
            seg[id].pb(mp(seg[id*2][p1].F, seg[id].back().S+1));
            p1++;
        }
        else {
            if (seg[id*2][p1].F < seg[id*2+1][p2].F) {
                seg[id].pb(mp(seg[id*2][p1].F, seg[id].back().S+1));
                p1++;
            }
            else {
                seg[id].pb(mp(seg[id*2+1][p2].F, seg[id].back().S));
                p2++;
            }
        }
    }
}
 
int get(int s, int e, int i, int j, int l = 0, int r = n, int id = 1) {
    if (j == i) return 0;
    if (s <= l and r <= e) return j-i;
    int mid = (l+r)/2, ans = 0;
    assert(i >= 0);
    assert(j >= 0);
    if (s < mid) ans += get(s, e, seg[id][i].S, seg[id][j].S, l, mid, id*2);
    if (e > mid) ans += get(s, e, i-seg[id][i].S, j-seg[id][j].S, mid, r, id*2+1);
    return ans;
}
 
int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q >> q;
    cin >> re[0]; re[0]--;
    oc[re[0]].pb(0);
    for (int i = 1; i < n; i++) {
        int p; cin >> p >> re[i]; re[i]--;
        adj[--p].pb(i);
        oc[re[i]].pb(i);
    }
    for (int i = 0; i < maxr; i++) {
        if (oc[i].size() >= sq) id[i] = cur++;
    }
    dfs();
    build();
    // for (pii p : seg[1]) cout << p.F << ' ' << p.S << '\n';
    while (q--) {
        int r1, r2; cin >> r1 >> r2; r1--, r2--;
        if (oc[r1].size() >= sq) cout << res[id[r1]][r2];
        else {
            int ans = 0;
            int l = lower_bound(all(seg[1]), mp(r2, -inf))-seg[1].begin()-1;
            int r = upper_bound(all(seg[1]), mp(r2, inf))-seg[1].begin()-1;
            // cout << l << ' ' << r << '\n';
            if (l != seg[1].size()) {
                for (int v : oc[r1]) ans += get(in[v], out[v], l, r);
            }
            cout << ans;
        }
        cout << endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int32_t main()':
regions.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             if (l != seg[1].size()) {
      |                 ~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 84568 KB Output is correct
2 Correct 14 ms 84568 KB Output is correct
3 Correct 12 ms 84568 KB Output is correct
4 Correct 14 ms 84568 KB Output is correct
5 Correct 16 ms 84820 KB Output is correct
6 Correct 20 ms 84824 KB Output is correct
7 Correct 27 ms 85080 KB Output is correct
8 Correct 35 ms 85080 KB Output is correct
9 Correct 54 ms 86336 KB Output is correct
10 Correct 84 ms 87344 KB Output is correct
11 Correct 147 ms 88284 KB Output is correct
12 Correct 185 ms 90456 KB Output is correct
13 Correct 220 ms 90448 KB Output is correct
14 Correct 390 ms 91812 KB Output is correct
15 Correct 527 ms 98308 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3413 ms 107456 KB Output is correct
2 Correct 3375 ms 106680 KB Output is correct
3 Correct 6924 ms 111172 KB Output is correct
4 Correct 304 ms 91920 KB Output is correct
5 Correct 414 ms 96784 KB Output is correct
6 Correct 467 ms 97880 KB Output is correct
7 Correct 1675 ms 105864 KB Output is correct
8 Correct 1425 ms 115412 KB Output is correct
9 Correct 5118 ms 131072 KB Output is correct
10 Runtime error 655 ms 131072 KB Execution killed with signal 9
11 Runtime error 816 ms 131072 KB Execution killed with signal 9
12 Runtime error 694 ms 131072 KB Execution killed with signal 9
13 Runtime error 643 ms 131072 KB Execution killed with signal 9
14 Runtime error 712 ms 131072 KB Execution killed with signal 9
15 Runtime error 753 ms 131072 KB Execution killed with signal 9
16 Runtime error 764 ms 131072 KB Execution killed with signal 9
17 Runtime error 790 ms 131072 KB Execution killed with signal 9