oj.uz

Submission #401508

# Submission time Handle Problem Language Result Execution time Memory
401508 2021-05-10T12:44:50 Z Drew_ Floppy (RMI20_floppy) C++14
100 / 100
 123 ms 10496 KB 
#include <stdlib.h>
#include <string.h>

#include "floppy.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

void read_array(int subtask_id, const std::vector<int> &v) {
	vector<int> st;
	string s;
    for (int i = 0; i < (int)v.size(); ++i)
    {
    	while (!st.empty() && st.back() < v[i])
    		s.pb('0'), st.pop_back();
    	s.pb('1'); st.pb(v[i]);
    }
    //cerr << "s: " << s << '\n';
    save_to_floppy(s);
}

std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
	const int MAX = 4e4 + 7;
	const int LG = (int)log2(MAX);

	int up[MAX][LG];

	vector<int> st;
	for (int i = 0, num = 0; i < (int)bits.size(); ++i)
	{
		if (bits[i] == '0')
			st.pop_back();
		else
		{
			if (st.empty()) up[num][0] = num;
			else up[num][0] = st.back();
			st.pb(num++);
		}
	}

	//for (int i = 0; i < N; ++i)
	//	cerr << i << ": " << up[i][0] << '\n';

	for (int j = 1; j < LG; ++j)
		for (int i = 0; i < N; ++i)
			up[i][j] = up[up[i][j-1]][j-1];

	vector<int> answers;
	for (int i = 0; i < (int) a.size(); ++i)
	{
		int l = a[i], r = b[i];
		for (int j = LG-1; j >= 0; --j)
			if (up[r][j] >= l)
				r = up[r][j];
		answers.pb(r);
	}

    return answers;
}

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 3 ms 772 KB Output is correct
2 Correct 3 ms 764 KB Output is correct
3 Correct 3 ms 772 KB Output is correct
4 Correct 3 ms 764 KB Output is correct
5 Correct 3 ms 784 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3068 KB Output is correct
2 Correct 28 ms 3048 KB Output is correct
3 Correct 27 ms 3000 KB Output is correct
4 Correct 32 ms 3036 KB Output is correct
5 Correct 27 ms 3132 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 10428 KB Output is correct
2 Correct 112 ms 10332 KB Output is correct
3 Correct 113 ms 10496 KB Output is correct
4 Correct 123 ms 10412 KB Output is correct
5 Correct 111 ms 10328 KB Output is correct