oj.uz

Submission #401624

# Submission time Handle Problem Language Result Execution time Memory
401624 2021-05-10T15:03:24 Z maximath_1 Floppy (RMI20_floppy) C++17
100 / 100
 151 ms 15160 KB 
#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;

const int MX = 1e5;
pair<int, int> st[MX * 4];
vector<int> _v;
int n;
string bits = "";

void build(int nd, int cl, int cr){
	if(cl == cr) return void(st[nd] = {_v[cl], cl});

	build(nd * 2, cl, (cl + cr) / 2);
	build(nd * 2 + 1, (cl + cr) / 2 + 1, cr);
	st[nd] = max(st[nd * 2], st[nd * 2 + 1]);
}

pair<int, int> que(int nd, int cl, int cr, int lf, int rg){
	if(lf > rg || cr < lf || rg < cl) return {-2000000000, -1};
	if(lf <= cl && cr <= rg) return st[nd];

	pair<int, int> L = que(nd * 2, cl, (cl + cr) / 2, lf, rg);
	pair<int, int> R = que(nd * 2 + 1, (cl + cr) / 2 + 1, cr, lf, rg);
	return max(L, R);
}

void create(int lf, int rg){
	int nw = que(1, 0, n - 1, lf, rg).second;
	if(lf <= nw - 1){
		bits += '1';
		create(lf, nw - 1);
	}else bits += '0';
	if(nw + 1 <= rg){
		bits += '1';
		create(nw + 1, rg);
	}else bits += '0';
}

void read_array(int subtask_id, const vector<int> &vv){
	_v = vv; n = _v.size();
	build(1, 0, n - 1);
	create(0, n - 1);
	save_to_floppy(bits);
}

void upd(int nd, int cl, int cr, int ps, int val){
	if(ps < cl || cr < ps) return;
	if(ps == cl && ps == cr) return void(st[nd] = {val, cl});

	upd(nd * 2, cl, (cl + cr) / 2, ps, val);
	upd(nd * 2 + 1, (cl + cr) / 2 + 1, cr, ps, val);
	st[nd] = max(st[nd * 2], st[nd * 2 + 1]);
}

int pt = 0, nw;
int lc[MX], rc[MX];
void create_graph(){
	int cr = nw;
	if(bits[pt ++] == '1'){
		nw --;
		lc[cr] = nw;
		create_graph();
	}else lc[cr] = -1;
	if(bits[pt ++] == '1'){
		nw --;
		rc[cr] = nw;
		create_graph();
	}else rc[cr] = -1;
}

int sz[MX];
void dfs(int nd, int tp = 0){
	sz[nd] = 1;
	if(lc[nd] != -1){
		dfs(lc[nd], tp);
		sz[nd] += sz[lc[nd]];
	}

	upd(1, 0, n - 1, tp + sz[nd] - 1, nd);

	if(rc[nd] != -1){
		dfs(rc[nd], tp + sz[nd]);
		sz[nd] += sz[rc[nd]];
	}
}

vector<int> solve_queries(int subtask_id, int N, const string &bis,
        const vector<int> &a, const vector<int> &b){
	bits = bis;
	n = N; nw = n;
	create_graph();
	dfs(n, 0);

	vector<int> ans(a.size());
	for(int i = 0; i < a.size(); i ++)
		ans[i] = que(1, 0, n - 1, a[i], b[i]).second;

	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:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 668 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 4 ms 768 KB Output is correct
4 Correct 3 ms 764 KB Output is correct
5 Correct 3 ms 764 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3660 KB Output is correct
2 Correct 37 ms 3776 KB Output is correct
3 Correct 36 ms 4204 KB Output is correct
4 Correct 36 ms 3884 KB Output is correct
5 Correct 36 ms 3700 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 14124 KB Output is correct
2 Correct 146 ms 14060 KB Output is correct
3 Correct 144 ms 15160 KB Output is correct
4 Correct 151 ms 15124 KB Output is correct
5 Correct 150 ms 14024 KB Output is correct