Submission #1224290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224290		MuhammadSaram	Floppy (RMI20_floppy)	C++20	28 / 100	35 ms	6492 KiB

floppy

#include <bits/stdc++.h>
#include "floppy.h"

using namespace std;

const int M = 40000, L = 16;

int maxx[M][L];

pair<int,int> get(int l,int r)
{
	int b=31-__builtin_clz(r-l);
	return {maxx[l][b],maxx[r-(1<<b)][b]};
}

void read_array(int subtask_id, const vector<int> &a)
{
	string s;
	int n=a.size();
	int lg=31-__builtin_clz(n-1);
	set<int> se;
	for (int i=0;i<n;i++) se.insert(a[i]);
	map<int,int> ind;
	for (int i:se) ind[i]=ind.size();
	vector<int> v;
	for (int i=0;i<n;i++)
		v.push_back(ind[a[i]]);
	for (int i=0;i<n;i++)
		for (int p=lg;p>=0;p--)
			s+=char('0'+(v[i]>>p)%2);
	save_to_floppy(s);
}

vector<int> solve_queries(int subtask_id, int n,
        const string &bits,
        const vector<int> &a, const vector<int> &b) {
    vector<int> ans;
	int lg=31-__builtin_clz(n-1);
	vector<int> v(n);
	int id=0;
	for (int i=0;i<n;i++)
		for (int p=lg;p>=0;p--)
			if (bits[id++]=='0')
				v[i]=v[i]*2;
			else
				v[i]=v[i]*2+1;
	for (int i=0;i<n;i++) maxx[i][0]=i;
	for (int p=1;p<L;p++)
		for (int i=0;i+(1<<p)<=n;i++)
		{
			maxx[i][p]=maxx[i][p-1];
			if (v[maxx[i+(1<<p-1)][p-1]]>v[maxx[i][p-1]])
				maxx[i][p]=maxx[i+(1<<p-1)][p-1];
		}
	for (int i=0;i<a.size();i++)
	{
		pair<int,int> p=get(a[i],b[i]+1);
		if (v[p.first]>v[p.second])
			ans.push_back(p.first);
		else
			ans.push_back(p.second);
	}
	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 0 / 72