oj.uz

답안 #898935

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
898935 2024-01-05T09:16:46 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 = 200000+1, maxr = 25000+1, sq = 401, sq_ = 501;
 
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();
    int amir = 0;
    for (int i = 0; i < n; i++) amir += seg[i].size();
    assert(amir < 6000000);
    // 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:102: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]
  102 |             if (l != seg[1].size()) {
      |                 ~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 74328 KB Output is correct
2 Correct 10 ms 74328 KB Output is correct
3 Correct 12 ms 74356 KB Output is correct
4 Correct 14 ms 74328 KB Output is correct
5 Correct 14 ms 74580 KB Output is correct
6 Correct 18 ms 74584 KB Output is correct
7 Correct 26 ms 74840 KB Output is correct
8 Correct 30 ms 74840 KB Output is correct
9 Correct 45 ms 76120 KB Output is correct
10 Correct 75 ms 77120 KB Output is correct
11 Correct 133 ms 78064 KB Output is correct
12 Correct 171 ms 80224 KB Output is correct
13 Correct 212 ms 80140 KB Output is correct
14 Correct 414 ms 81560 KB Output is correct
15 Correct 504 ms 88012 KB Output is correct

Subtask #2
65.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3402 ms 97068 KB Output is correct
2 Correct 3487 ms 96440 KB Output is correct
3 Correct 6268 ms 101116 KB Output is correct
4 Correct 308 ms 81720 KB Output is correct
5 Correct 405 ms 86840 KB Output is correct
6 Correct 454 ms 87812 KB Output is correct
7 Correct 1966 ms 95852 KB Output is correct
8 Correct 1425 ms 105292 KB Output is correct
9 Correct 4667 ms 121296 KB Output is correct
10 Correct 6988 ms 129916 KB Output is correct
11 Execution timed out 8029 ms 126996 KB Time limit exceeded
12 Correct 3447 ms 127196 KB Output is correct
13 Correct 4468 ms 127720 KB Output is correct
14 Correct 4587 ms 128616 KB Output is correct
15 Runtime error 719 ms 131072 KB Execution killed with signal 9
16 Runtime error 683 ms 131072 KB Execution killed with signal 9
17 Runtime error 612 ms 131072 KB Execution killed with signal 9