oj.uz

답안 #898884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
898884 2024-01-05T08:42:32 Z Amirreza_Fakhri Regions (IOI09_regions) C++17
19 / 100
 943 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);
    assert(j >= i);
    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:100: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]
  100 |             if (l != seg[1].size()) {
      |                 ~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 123736 KB Output is correct
2 Correct 18 ms 123736 KB Output is correct
3 Correct 16 ms 123736 KB Output is correct
4 Correct 18 ms 123736 KB Output is correct
5 Correct 22 ms 123728 KB Output is correct
6 Correct 25 ms 123992 KB Output is correct
7 Correct 33 ms 123908 KB Output is correct
8 Correct 38 ms 123992 KB Output is correct
9 Correct 52 ms 125364 KB Output is correct
10 Correct 98 ms 126380 KB Output is correct
11 Correct 161 ms 127312 KB Output is correct
12 Correct 184 ms 129444 KB Output is correct
13 Correct 236 ms 129404 KB Output is correct
14 Correct 417 ms 130828 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 116 ms 131072 KB Execution killed with signal 9
2 Runtime error 139 ms 131072 KB Execution killed with signal 9
3 Runtime error 135 ms 131072 KB Execution killed with signal 9
4 Correct 332 ms 130984 KB Output is correct
5 Runtime error 192 ms 131072 KB Execution killed with signal 9
6 Runtime error 228 ms 131072 KB Execution killed with signal 9
7 Runtime error 432 ms 131072 KB Execution killed with signal 9
8 Runtime error 339 ms 131072 KB Execution killed with signal 9
9 Runtime error 243 ms 131072 KB Execution killed with signal 9
10 Runtime error 51 ms 131072 KB Execution killed with signal 9
11 Runtime error 943 ms 131072 KB Execution killed with signal 9
12 Runtime error 56 ms 131072 KB Execution killed with signal 9
13 Runtime error 53 ms 131072 KB Execution killed with signal 9
14 Runtime error 54 ms 131072 KB Execution killed with signal 9
15 Runtime error 55 ms 131072 KB Execution killed with signal 9
16 Runtime error 63 ms 131072 KB Execution killed with signal 9
17 Runtime error 57 ms 131072 KB Execution killed with signal 9