oj.uz

Submission #596631

# Submission time Handle Problem Language Result Execution time Memory
596631 2022-07-14T22:32:16 Z vh50 Floppy (RMI20_floppy) C++17
0 / 100
 31 ms 2768 KB 
#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
const int MAXN = 5e5;
pair <int, int> seg[MAXN];
void update(int cur, int ini, int fim, int id, int val)
{
	if(id < ini || fim < id)	return;
	if(ini == fim)
	{
		seg[cur] = {cur, val};
		return;
	}
	int m = (ini + fim)/2;
	update(2 * cur, ini, m, id, val);
	update(2 * cur + 1, m + 1, fim, id, val);
	if(seg[2 * cur].second < seg[2 * cur + 1].second)	seg[cur] = seg[2 * cur + 1];
	else seg[cur] = seg[2 * cur];
}

pair <int, int> query(int cur, int ini, int fim, int p, int q)
{
	if(fim < p || q < ini)	return {-1, -1};
	if(p <= ini && fim <= q)	return seg[cur];
	int m = (ini + fim)/2;
	pair <int, int> aux1 = query(2 * cur, ini, m, p, q), aux2 = query(2 * cur + 1, m + 1, fim, p, q);
	if(aux1.second < aux2.second)	return aux2;
	return aux1;
}

void read_array(int subtask_id, const vector<int> &v) {
    string bits;
	for(int x : v) 
		for(int i = 20; i >= 0; i--)
			if(x & (1 << i))	bits.push_back('1');
			else	bits.push_back('0');
	save_to_floppy(bits); 
} 

vector <int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const std::vector<int> &b) 
{
	vector<int> answers;
	int aux = 0, k = 0;
	for(int i = 0; i < bits.size(); i++)
	{
		if(i % 20 == 0 && i != 0)
		{
			update(1, 1, N, k + 1, aux);
			aux = 0;
			k++;
		}
		if(bits[i] == '1')
		{
			int ex = 20 - (i % 20);
			if(ex == 20)	ex = 0;
			aux += (1 << ex);
		}	
	}
	for(int i = 0; i < a.size(); i++)
	{
		answers.push_back(query(1, 1, N, a[i] + 1, b[i] + 1).first - 1);
	}
	return answers; 
}

Compilation message

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i = 0; i < bits.size(); i++)
      |                 ~~^~~~~~~~~~~~~
floppy.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0; i < a.size(); i++)
      |                 ~~^~~~~~~~~~
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 Incorrect 2 ms 792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1192 KB L is too large
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 2768 KB L is too large
2 Halted 0 ms 0 KB -