oj.uz

Submission #898912

# Submission time Handle Problem Language Result Execution time Memory
898912 2024-01-05T08:58:58 Z Amirreza_Fakhri Regions (IOI09_regions) C++17
80 / 100
 8000 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+1, maxr = 25e3, sq = 501, sq_ = 401;
 
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 <pair <short, int> > 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((short)r2, -inf))-seg[1].begin()-1;
            int r = upper_bound(all(seg[1]), mp((short)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<short 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 14 ms 64088 KB Output is correct
2 Correct 10 ms 64088 KB Output is correct
3 Correct 10 ms 64088 KB Output is correct
4 Correct 12 ms 64088 KB Output is correct
5 Correct 14 ms 64344 KB Output is correct
6 Correct 21 ms 64344 KB Output is correct
7 Correct 25 ms 64376 KB Output is correct
8 Correct 32 ms 64856 KB Output is correct
9 Correct 44 ms 65884 KB Output is correct
10 Correct 73 ms 66904 KB Output is correct
11 Correct 132 ms 67832 KB Output is correct
12 Correct 167 ms 69892 KB Output is correct
13 Correct 198 ms 69916 KB Output is correct
14 Correct 390 ms 71364 KB Output is correct
15 Correct 502 ms 77844 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3604 ms 86816 KB Output is correct
2 Correct 3553 ms 86208 KB Output is correct
3 Correct 6217 ms 90788 KB Output is correct
4 Correct 261 ms 71560 KB Output is correct
5 Correct 373 ms 76748 KB Output is correct
6 Correct 2178 ms 77660 KB Output is correct
7 Correct 2794 ms 85948 KB Output is correct
8 Correct 2660 ms 95360 KB Output is correct
9 Correct 4837 ms 111404 KB Output is correct
10 Execution timed out 8028 ms 119964 KB Time limit exceeded
11 Execution timed out 8069 ms 117312 KB Time limit exceeded
12 Correct 3184 ms 117588 KB Output is correct
13 Correct 4573 ms 118024 KB Output is correct
14 Correct 4387 ms 118884 KB Output is correct
15 Execution timed out 8018 ms 124096 KB Time limit exceeded
16 Runtime error 454 ms 131072 KB Execution killed with signal 9
17 Correct 6648 ms 130140 KB Output is correct