oj.uz

Submission #533790

# Submission time Handle Problem Language Result Execution time Memory
533790 2022-03-07T09:01:37 Z amunduzbaev Floppy (RMI20_floppy) C++17
0 / 100
 33 ms 9292 KB 
#include "bits/stdc++.h"
using namespace std;
#include "floppy.h"
#ifndef EVAL
#include "grader.cpp"
#endif

const int MAX = 4e4 + 5;
int st[MAX][20];

void read_array(int QOQ, const vector<int> &v) {
	int n = (int)v.size();
	for(int i=0;i<n;i++) st[i][0] = i;
	for(int j=1;j<20;j++){
		int d = (1 << (j - 1));
		for(int i=0;i + d < n;i++){
			st[i][j] = st[i][j-1];
			if(v[st[i + d][j-1]] > v[st[i][j]]){
				st[i][j] = st[i + d][j-1];
			}
		}
	}
	
	auto get = [&](int l, int r){
		int lg = __lg(r - l + 1);
		if(v[st[l][lg]] >= v[st[r - (1 << lg) + 1][lg]]) return st[l][lg];
		return st[r - (1 << lg) + 1][lg];
	};
	
	string res(4 * n, '0');
	function<void(int, int, int)> rec = [&](int l, int r, int x){
		int m = get(l, r);
		if(l < m) res[x << 1] = '1', rec(l, m - 1, x << 1);
		if(m < r) res[x << 1 | 1] = '1', rec(m + 1, r, x << 1 | 1);
	};
	
	rec(0, n - 1, 1);
	save_to_floppy(res);
}

/*

3
4 10
4 2 3 1
0 0 0
0 1 0
0 2 0
0 3 0
1 1 1
1 2 2
1 3 2
2 2 2
2 3 2
3 3 3

*/

vector<int> solve_queries(int QOQ, int n, const string &tree, const vector<int> &a, const vector<int> &b) {
	int m = a.size();
	
	vector<int> v(n, -1);
	int p = 0;
	function<int(int)> rec = [&](int x){
		int mx = 0;
		if(tree[x<<1] == '1') mx = max(mx, rec(x<<1) + 1);
		int pos = p++;
		if(tree[x<<1|1] == '1') mx = max(mx, rec(x<<1|1) + 1);
		v[pos] = mx;
		return mx;
	};
	
	rec(1);
	//~ for(int i=0;i<n;i++) cout<<v[i]<<" ";
	//~ cout<<"\n";
	
	for(int i=0;i<n;i++){
		st[i][0] = i;
		assert(~v[i]);
	}
	for(int j=1;j<20;j++){
		int d = (1 << (j - 1));
		for(int i=0;i + d < n;i++){
			st[i][j] = st[i][j-1];
			if(v[st[i + d][j-1]] > v[st[i][j]]){
				st[i][j] = st[i + d][j-1];
			}
		}
	}
	auto get = [&](int l, int r){
		int lg = __lg(r - l + 1);
		if(v[st[l][lg]] >= v[st[r - (1 << lg) + 1][lg]]) return st[l][lg];
		return st[r - (1 << lg) + 1][lg];
	};
	
	vector<int> res;
	for(int i=0;i<m;i++){
		res.push_back(get(a[i], b[i]));
	} return res;
}

Compilation message

stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if (query_answers.size() != M) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2636 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 9292 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -