oj.uz

Submission #596632

# Submission time Handle Problem Language Result Execution time Memory
596632 2022-07-14T22:49:52 Z pedroslrey Floppy (RMI20_floppy) C++17
100 / 100
 97 ms 14496 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3092 KB Output is correct
2 Correct 3 ms 3176 KB Output is correct
3 Correct 3 ms 3236 KB Output is correct
4 Correct 2 ms 3188 KB Output is correct
5 Correct 4 ms 3108 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5064 KB Output is correct
2 Correct 24 ms 5852 KB Output is correct
3 Correct 26 ms 5712 KB Output is correct
4 Correct 26 ms 5872 KB Output is correct
5 Correct 26 ms 5852 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 10984 KB Output is correct
2 Correct 97 ms 14464 KB Output is correct
3 Correct 96 ms 14296 KB Output is correct
4 Correct 96 ms 14496 KB Output is correct
5 Correct 96 ms 14448 KB Output is correct