Submission #596632

#	Time	Username	Problem	Language	Result	Execution time	Memory
596632		pedroslrey	Floppy (RMI20_floppy)	C++17	100 / 100	97 ms	14496 KiB

floppy

#include <bits/stdc++.h>
#include "floppy.h"

using namespace std;

const int MAXN = 4e4 + 10;

int xs[MAXN], lst[MAXN];

void read_array(int fodase, const vector<int> &vs) {
	int n = vs.size();
	for (int i = 0; i < n; ++i)
		xs[i + 1] = vs[i];

	string s = "";
	xs[0] = 2e9;
	for (int i = 1; i <= n; ++i) {
		int atual = i - 1;
		while (xs[atual] <= xs[i]) {
			atual = lst[atual];
			s += '0';
		}
		lst[i] = atual;
		s += '1';
	}

	save_to_floppy(s);
}

struct node {
	int val, idx;

	node(int v = 2e9, int i = 0) : val {v}, idx {i} { }

	node operator+(node other) {
		if (val < other.val) return *this;
		if (other.val < val) return other;
		return node(val, max(idx, other.idx));
	}
};

node seg[4*MAXN];

void build(int pos, int ini, int fim) {
	if (ini == fim) {
		seg[pos] = node(lst[ini], ini);
		return;
	}

	int m = (ini + fim)/2;
	build(2*pos, ini, m);
	build(2*pos + 1, m + 1, fim);

	seg[pos] = seg[2*pos] + seg[2*pos + 1];
}

node query(int pos, int ini, int fim, int l, int r) {
	if (l <= ini && fim <= r) return seg[pos];
	if (fim < l || r < ini) return node();

	int m = (ini + fim)/2;
	return query(2*pos, ini, m, l, r) + query(2*pos + 1, m + 1, fim, l, r);
}

vector<int> solve_queries(int fodase, int n, const string &s, const vector<int> &ls, const vector<int> &rs) {
	int stop = 0;
	for (int i = 1; i <= n; ++i) {
		lst[i] = i-1;
		while (s[stop] == '0') {
			lst[i] = lst[lst[i]];
			++stop;
		}
		++stop;
	}

	build(1, 1, n);

	vector<int> ans;
	for (int i = 0; i < ls.size(); ++i)
		ans.push_back(query(1, 1, n, ls[i]+1, rs[i]+1).idx - 1);
	return ans;
}

Compilation message (stderr)

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < ls.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: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72