QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#773164 | #28. Corporate life (after hostile takover) | IBory | 0 | 3ms | 7752kb | C++20 | 1.4kb | 2024-11-23 02:37:39 | 2024-11-23 02:37:39 |
answer
#include <bits/stdc++.h>
using namespace std;
const int SZ = 1 << 18;
vector<int> G[2][SZ];
int in[2][SZ], out[2][SZ], dn;
struct Seg {
vector<int> T[SZ << 1];
void Build() {
for (int i = SZ - 1; i > 0; --i) {
T[i].resize(T[i * 2].size() + T[i * 2 + 1].size());
merge(T[i * 2].begin(), T[i * 2].end(), T[i * 2 + 1].begin(), T[i * 2 + 1].end(), T[i].begin());
}
}
int Query(int L, int R, int l, int r, int sL = 1, int sR = SZ, int n = 1) {
if (R < sL || sR < L) return 0;
if (L <= sL && sR <= R) {
auto itR = upper_bound(T[n].begin(), T[n].end(), r);
auto itL = lower_bound(T[n].begin(), T[n].end(), l);
return itR - itL;
}
int mid = (sL + sR) >> 1;
return (Query(L, R, l, r, sL, mid, n * 2) + Query(L, R, l, r, mid + 1, sR, n * 2 + 1));
}
} T;
void DFS(int cur, int k) {
in[k][cur] = ++dn;
for (int next : G[k][cur]) DFS(next, k);
out[k][cur] = dn;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N;
cin >> N;
for (int t = 0; t < 2; ++t) {
for (int i = 2; i <= N; ++i) {
int p;
cin >> p;
G[t][p].push_back(i);
}
dn = 0;
DFS(1, t);
}
for (int i = 1; i <= N; ++i) T.T[in[1][i] + SZ - 1].push_back(in[0][i]);
T.Build();
return 0;
for (int i = 1; i <= N; ++i) {
int l = in[0][i], r = out[0][i];
int ans = T.Query(in[1][i], out[1][i], l, r) - 1;
cout << ans << ' ';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 7752kb
input:
100 63 76 68 34 53 59 51 62 82 2 90 61 40 85 46 23 34 39 73 23 36 35 61 62 53 95 72 77 17 38 44 34 82 16 18 12 53 23 50 22 1 34 95 34 31 42 10 38 17 58 4 99 68 54 31 36 11 32 54 41 42 59 68 27 60 100 11 40 39 53 83 98 50 69 98 42 74 9 95 95 25 42 87 55 90 43 55 75 14 35 60 20 6 12 22 68 13 3 51 82 5...
output:
result:
wrong answer 1st lines differ - expected: '99 13 26 0 0 0 0 0 0 0 16 0 0 ...0 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0', found: ''
Subtask #2:
score: 0
Skipped
Dependency #1:
0%