Submission #603642

#	Time	Username	Problem	Language	Result	Execution time	Memory
603642		CSQ31	Floppy (RMI20_floppy)	C++17	28 / 100	56 ms	6696 KiB

floppy

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

void read_array(int subtask_id, const vector<int> &v) {
	int n = v.size();
	vector<array<int,2>>u(n);
	for(int i=0;i<n;i++)u[i] = {v[i],i};
	sort(u.begin(),u.end());
	vector<int>pos(n);
	for(int i=0;i<n;i++)pos[u[i][1]] = i;
	string bits;
	for(int i=0;i<n;i++){
		for(int j=0;j<14;j++){
			if(pos[i]&(1<<j))bits+="1";
			else bits+="0";
			
		}
	}
	
    save_to_floppy(bits);
}
array<int,2>T[100000],t[1000000];
void build(int v,int l,int r){
	if(l==r){
		t[v] = T[l];
		return;
	}
	int tm = (l+r)/2;
	build(2*v,l,tm);
	build(2*v+1,tm+1,r);
	t[v] = max(t[2*v],t[2*v+1]);
	
}
array<int,2>query(int v,int l,int r,int tl,int tr){
	if(l>r)return {-1,-1};
	if(l==tl && r==tr)return t[v];
	int tm = (tl+tr)/2;
	return max(query(2*v,l,min(tm,r),tl,tm),
	           query(2*v+1,max(l,tm+1),r,tm+1,tr));
}
vector<int> solve_queries(int subtask_id, int n,const string &bits,const vector<int> &a, const std::vector<int> &b) {
	int c = 0;
	for(int i=0;i<n;i++){
		for(int j=0;j<14;j++){
			if(bits[c] == '1')T[i][0]+=(1<<j);
			c++;
		}
		T[i][1] = i;
	}
	build(1,0,n-1);
	int q = a.size();
    vector<int> answers(q);
    for(int i=0;i<q;i++){
		answers[i] = query(1,a[i],b[i],0,n-1)[1];
	}

    return answers;
}

Compilation message (stderr)

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: 0 / 72