Company Queries II

input/code.cpp: In function 'void print_matrix(std::vector<std::vector<int> >, std::string)':
input/code.cpp:32:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i = 0; i < in.size(); i++) {
      |                         ~~^~~~~~~~~~~
input/code.cpp:33:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                 for (int j = 0; j < in[i].size(); j++) {
      |                                 ~~^~~~~~~~~~~~~~
input/code.cpp: In function 'void build_sparse_table(std::vector<int>&, std::vector<std::vector<int> >&)':
input/code.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int i = 0; i < in.size(...

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <utility>
#include <vector>
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#else
#define deb(fmt, args...)
#endif
 
void print_array(vector<int> in, const string title = "Vector")
{
	cout << title << " [\n";
	for (const auto &el : in) {
		cout << el << " ";
	}
	cout << "\n] END\n";
}
 
void print_matrix(vector<vector<int> > in, const string title = "Matrix")
{
	cout << title << " [\n";
	for (int i = 0; i < in.size(); i++) {
		for (int j = 0; j < in[i].size(); j++) {
			cout << in[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "] END\n";
}
 
void dfs(int s, vector<bool> visited, vector<vector<int>> adj, vector<int> &traversal)
{
	if (visited[s]) {
		return;
	};
	visited[s] = true;
 
	traversal.push_back(s);
	for (auto u : adj[s]) {
		dfs(u, visited, adj, traversal);
		traversal.push_back(s);
	}
}
 
void build_sparse_table(vector<int> &in, vector<vector<int> > &sparse)
{
	int rows = in.size() % 2 == 0 ? in.size() / 2 : in.size() / 2 + 1;
	sparse.clear(); // clear table
	sparse.push_back(vector<int>()); // needed rows
	for (int i = 0; i < in.size(); i++) {
		sparse[0].push_back(in[i]);
	}
	for (int i = 1; i < rows; i++) {
		sparse.push_back(vector<int>()); // needed rows
		int len = 1
			  << (i - 1); // len * 2 is the interval for this round
		for (int j = 0; j < in.size() - len; j++) {
			sparse[i].push_back(
				min(sparse[i - 1][j], sparse[i - 1][j + len]));
		}
	}
}
 
int query_sparse_table(int a, int b, vector<vector<int> > &sparse)
{
	int L = min(a, b);
	int R = max(a, b);
	int num = 1;
	while (num < R - L)
		num <<= 1;
	num >>= 1; // To get the number below the range width
	int row = num >> 1; // to get the row number
	return min(sparse[row][a], sparse[row][b - num]);
}
 
int main(int argc, char *argv[])
{
	// Read the input parameters
	int n, q;
	cin >> n >> q;
 
	// Read values from one line
	vector<vector<int>> kids(n + 1, vector<int>());
	int tmp;
	for (int i = 2; i < n + 1; i++) {
		cin >> tmp;
		kids[tmp].push_back(i);
	}
 
	// print_matrix(kids);
 
	vector<bool> visited(n, false);
	vector<int> traversal;
	dfs(1, visited, kids, traversal);
	// print_array(traversal);
	// vector<int> traversal = { 1, 3, 4, 8, 6, 1, 4, 2 };
	vector<vector<int> > sparse(1, vector<int>());
	build_sparse_table(traversal, sparse);
	// print_matrix(sparse);
 
	// Read pairs from multiple lines
	vector<pair<int, int>> input_pairs(q);
	int l, r;
	for (int i = 0; i < q; i++) {
		cin >> l >> r;
		cout << query_sparse_table(l - 1, r - 1, sparse) << "\n";
	}
 
	return 0;
}

Test 1

Verdict: RUNTIME ERROR

Test 2

Verdict: RUNTIME ERROR

Test 3

Verdict: RUNTIME ERROR

Test 4

Verdict: RUNTIME ERROR

Test 5

Verdict: RUNTIME ERROR

Test 6

Verdict: RUNTIME ERROR

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: RUNTIME ERROR

Test 10

Verdict: RUNTIME ERROR

Test 11

Verdict: ACCEPTED

Test 12

Verdict: RUNTIME ERROR