This is the question for which the implementation is mentioned below
Basics of Implementation & Basic Programming Practice Problems
#include<bits/stdc++.h>
using namespace std;const int INF = 1e9;const int N = 100031;int n, tests;
int level[N];
vector<pair<int, int> > v;int ans[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> tests;
for (int i = 0; i < n; i++){
cin >> level[i];
}
v.clear();
for (int i = 0; i < n; i++){
v.push_back(make_pair(level[i], i));
}
for (int i = 0; i < n; i++)ans[i] = 0;while (v.size()>1){
vector<pair<int, int> > v2;for (int i = 0; i < v.size(); i += 2){
if (i + 1 == v.size()){
v2.push_back(v[i]);
continue;
}
ans[v[i].second]++;
ans[v[i + 1].second]++;if (v[i].first>v[i + 1].first)v2.push_back(v[i]);
else
v2.push_back(v[i + 1]);}
v = v2;
}
for (; tests; --tests){
int val;
cin >> val;
--val;
cout << ans[val] << "\n";}
return 0;}
---------
I'm not sure about the complexity of this code. I believe it's O(log(n)^2).
Or is it just O(n), as N elements are input in the first loop at the beginning
Let me explain my rationale. The loop
(while (v.size()>1) { .. } )
runs log(n)[ explanation.. first there are N then N/2 , then N/4 elements .. till there is just 1 element left ] so that's a complexity of log(N) ,
However the inner loop too runs in log(n) time, each time, but n is variable each time.
vector<pair<int, int> > v2;for (int i = 0; i < v.size(); i += 2){
if (i + 1 == v.size()){
v2.push_back(v[i]);
continue;
}
ans[v[i].second]++;
ans[v[i + 1].second]++;if (v[i].first>v[i + 1].first)v2.push_back(v[i]);
else
v2.push_back(v[i + 1]);}
v = v2;