This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define N 100005
const bool debug = 0;
int n, q, p[N][30], op, x, fen[N], L;
vector<int> adj[N], ord;
bool mark[N];
void add(int i, int val) {
for (; i<=n; i+=i&(-i)) fen[i] += val;
return;
}
int sum(int i) {
int ret = 0;
for (; i>0; i-=i&(-i)) ret += fen[i];
return ret;
}
int find_first(int l, int r) {
if (l == r) return l;
int m = (l+r)/2;
if (sum(m) == 0) find_first(m+1, r);
else find_first(l, m);
}
void find_ord(int v) {
for (int i=1; i<=L; i++) p[v][i] = p[p[v][i-1]][i-1];
for (auto to : adj[v]) {
if (to == p[v][0]) continue;
find_ord(to);
}
ord.push_back(v);
return;
}
pair<int, int> find_lift(int v) {
int ti = 0;
for (int i=L; i>=0; i--) {
if (!mark[p[v][i]]) v = p[v][i], ti += pow(2, i);
}
return make_pair(v, ti);
}
int main() {
scanf(" %d %d", &n, &q);
L = ceil(log2(n+.0));
for (int i=1; i<=n; i++) {
scanf(" %d", &p[i][0]);
adj[p[i][0]].push_back(i);
}
ord.push_back(0);
find_ord(adj[0][0]);
if (debug) {
cout << "ord ";
for (auto it : ord) cout << it << ' ';
cout << endl;
for (int i=1; i<=n; i++) {
cout << "b lift " << i << " : ";
for (int j=0; j<=L; j++) cout << p[i][j] << ' ';
cout << endl;
}
}
mark[0] = true;
for (int i=1; i<=n; i++) add(i, 1), mark[i] = true;
while (q--) {
scanf(" %d %d", &op, &x);
if (op == 1) {
int idx;
for (int i=1; i<=x; i++) {
idx = find_first(1, n);
add(idx, -1);
mark[ord[idx]] = false;
if (debug) {
cout << "fill " << i << " at: " << ord[idx] << endl;
}
}
printf("%d\n", ord[idx]);
}
else {
pair<int, int> p = find_lift(x);
add(p.first, 1);
mark[p.first] = true;
printf("%d\n", p.second);
}
}
return 0;
}
Compilation message (stderr)
ballmachine.cpp: In function 'int find_first(int, int)':
ballmachine.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
26 | }
| ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf(" %d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf(" %d", &p[i][0]);
| ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf(" %d %d", &op, &x);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |