Submission #401624

#	Time	Username	Problem	Language	Result	Execution time	Memory
401624		maximath_1	Floppy (RMI20_floppy)	C++17	100 / 100	151 ms	15160 KiB

floppy

#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 (stderr)

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 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72