oj.uz

답안 #898890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
898890 2024-01-05T08:47:13 Z Amirreza_Fakhri Regions (IOI09_regions) C++17
19 / 100
 1016 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 = 200, sq_ = 1e3+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
14.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 123736 KB Output is correct
2 Correct 15 ms 123724 KB Output is correct
3 Correct 16 ms 123736 KB Output is correct
4 Correct 17 ms 123788 KB Output is correct
5 Correct 19 ms 123736 KB Output is correct
6 Correct 25 ms 123980 KB Output is correct
7 Correct 32 ms 123992 KB Output is correct
8 Correct 36 ms 123992 KB Output is correct
9 Correct 50 ms 125368 KB Output is correct
10 Correct 87 ms 126380 KB Output is correct
11 Correct 173 ms 127316 KB Output is correct
12 Correct 171 ms 129392 KB Output is correct
13 Correct 247 ms 129392 KB Output is correct
14 Correct 424 ms 130816 KB Output is correct
15 Runtime error 76 ms 131072 KB Execution killed with signal 9

Subtask #2
5.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 121 ms 131072 KB Execution killed with signal 9
2 Runtime error 125 ms 131072 KB Execution killed with signal 9
3 Runtime error 129 ms 131072 KB Execution killed with signal 9
4 Correct 354 ms 130992 KB Output is correct
5 Runtime error 153 ms 131072 KB Execution killed with signal 9
6 Runtime error 223 ms 131072 KB Execution killed with signal 9
7 Runtime error 389 ms 131072 KB Execution killed with signal 9
8 Runtime error 361 ms 131072 KB Execution killed with signal 9
9 Runtime error 283 ms 131072 KB Execution killed with signal 9
10 Runtime error 56 ms 131072 KB Execution killed with signal 9
11 Runtime error 1016 ms 131072 KB Execution killed with signal 9
12 Runtime error 64 ms 131072 KB Execution killed with signal 9
13 Runtime error 62 ms 131072 KB Execution killed with signal 9
14 Runtime error 53 ms 131072 KB Execution killed with signal 9
15 Runtime error 71 ms 131072 KB Execution killed with signal 9
16 Runtime error 54 ms 131072 KB Execution killed with signal 9
17 Runtime error 62 ms 131072 KB Execution killed with signal 9