oj.uz

답안 #898887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
898887 2024-01-05T08:44:12 Z Amirreza_Fakhri Regions (IOI09_regions) C++17
30 / 100
 1535 ms 131076 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];

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

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 109400 KB Output is correct
2 Correct 12 ms 109232 KB Output is correct
3 Correct 13 ms 109400 KB Output is correct
4 Correct 14 ms 109400 KB Output is correct
5 Correct 19 ms 109400 KB Output is correct
6 Correct 21 ms 109400 KB Output is correct
7 Correct 32 ms 109656 KB Output is correct
8 Correct 34 ms 109656 KB Output is correct
9 Correct 50 ms 111000 KB Output is correct
10 Correct 91 ms 112024 KB Output is correct
11 Correct 153 ms 112948 KB Output is correct
12 Correct 194 ms 115128 KB Output is correct
13 Correct 238 ms 115040 KB Output is correct
14 Correct 431 ms 116456 KB Output is correct
15 Correct 551 ms 122940 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 156 ms 131072 KB Execution killed with signal 9
2 Runtime error 184 ms 131072 KB Execution killed with signal 9
3 Runtime error 208 ms 131072 KB Execution killed with signal 9
4 Correct 373 ms 116672 KB Output is correct
5 Correct 509 ms 121732 KB Output is correct
6 Correct 570 ms 122804 KB Output is correct
7 Runtime error 457 ms 131072 KB Execution killed with signal 9
8 Runtime error 560 ms 131072 KB Execution killed with signal 9
9 Runtime error 1138 ms 131072 KB Execution killed with signal 9
10 Runtime error 1270 ms 131072 KB Execution killed with signal 9
11 Runtime error 1535 ms 131072 KB Execution killed with signal 9
12 Runtime error 1272 ms 131072 KB Execution killed with signal 9
13 Runtime error 1331 ms 131076 KB Execution killed with signal 9
14 Runtime error 1310 ms 131072 KB Execution killed with signal 9
15 Runtime error 1383 ms 131072 KB Execution killed with signal 9
16 Runtime error 1236 ms 131072 KB Execution killed with signal 9
17 Runtime error 1217 ms 131072 KB Execution killed with signal 9