oj.uz

Submission #898892

# Submission time Handle Problem Language Result Execution time Memory
898892 2024-01-05T08:48:31 Z Amirreza_Fakhri Regions (IOI09_regions) C++17
55 / 100
 6307 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 = 300, sq_ = 670+5;
 
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 92760 KB Output is correct
2 Correct 12 ms 92900 KB Output is correct
3 Correct 13 ms 92760 KB Output is correct
4 Correct 14 ms 93208 KB Output is correct
5 Correct 16 ms 93016 KB Output is correct
6 Correct 23 ms 93016 KB Output is correct
7 Correct 28 ms 93272 KB Output is correct
8 Correct 33 ms 93272 KB Output is correct
9 Correct 47 ms 94516 KB Output is correct
10 Correct 86 ms 95604 KB Output is correct
11 Correct 142 ms 96424 KB Output is correct
12 Correct 186 ms 98572 KB Output is correct
13 Correct 217 ms 98476 KB Output is correct
14 Correct 405 ms 99876 KB Output is correct
15 Correct 517 ms 106456 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3221 ms 115404 KB Output is correct
2 Correct 3662 ms 114668 KB Output is correct
3 Correct 6307 ms 119044 KB Output is correct
4 Correct 297 ms 99948 KB Output is correct
5 Correct 452 ms 104868 KB Output is correct
6 Correct 503 ms 105836 KB Output is correct
7 Correct 1509 ms 113864 KB Output is correct
8 Correct 1502 ms 123212 KB Output is correct
9 Runtime error 653 ms 131072 KB Execution killed with signal 9
10 Runtime error 681 ms 131072 KB Execution killed with signal 9
11 Runtime error 884 ms 131072 KB Execution killed with signal 9
12 Runtime error 747 ms 131072 KB Execution killed with signal 9
13 Runtime error 780 ms 131072 KB Execution killed with signal 9
14 Runtime error 810 ms 131072 KB Execution killed with signal 9
15 Runtime error 854 ms 131072 KB Execution killed with signal 9
16 Runtime error 879 ms 131072 KB Execution killed with signal 9
17 Runtime error 792 ms 131072 KB Execution killed with signal 9