oj.uz

Submission #533795

# Submission time Handle Problem Language Result Execution time Memory
533795 2022-03-07T09:12:00 Z amunduzbaev Floppy (RMI20_floppy) C++17
100 / 100
 92 ms 21580 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(2 * n, '0');
	int last = 0;
	function<void(int, int, int)> rec = [&](int l, int r, int x){
		int m = get(l, r);
		//~ cout<<m<<" "<<x<<"\n";
		if(l < m) res[x<<1] = '1', rec(l, m - 1, ++last);
		if(m < r) res[x<<1|1] = '1', rec(m + 1, r, ++last);
	};
	
	rec(0, n - 1, 0);
	//~ cout<<"\n";
	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;
	int last = 0;
	function<int(int)> rec = [&](int x){
		int mx = 0;
		if(tree[x<<1] == '1') mx = max(mx, rec(++last) + 1);
		int pos = p++;
		if(tree[x<<1|1] == '1') mx = max(mx, rec(++last) + 1);
		v[pos] = mx;
		//~ cout<<pos<<" "<<x<<"\n";
		return mx;
	};
	
	rec(0);
	//~ 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 776 KB Output is correct
2 Correct 2 ms 784 KB Output is correct
3 Correct 2 ms 780 KB Output is correct
4 Correct 2 ms 792 KB Output is correct
5 Correct 2 ms 760 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3964 KB Output is correct
2 Correct 21 ms 4720 KB Output is correct
3 Correct 21 ms 5712 KB Output is correct
4 Correct 21 ms 5268 KB Output is correct
5 Correct 21 ms 4644 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 14360 KB Output is correct
2 Correct 86 ms 17884 KB Output is correct
3 Correct 84 ms 21580 KB Output is correct
4 Correct 92 ms 19632 KB Output is correct
5 Correct 85 ms 17880 KB Output is correct