Submission #1224215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224215		Muhammad_Aneeq	Floppy (RMI20_floppy)	C++20	28 / 100	28 ms	2912 KiB

floppy

#include <stdlib.h>
#include <string.h>
#include <cmath>
#include <algorithm>
#include "floppy.h"
using namespace std;
int const MAXN=2e4+10,LG=15;
int mx[MAXN][LG]={};
int get(int l,int r)
{
    int lg=log2(r-l+1);
    return max(mx[l][lg],mx[r+1-(1<<lg)][lg]);
}
void read_array(int subtask_id, const std::vector<int> &V) {
    int n=V.size();
    int lg=log2(n)+1;
    vector<int>x,v;
    for (auto i:V)
        x.push_back(i);
    sort(begin(x),end(x));
    v=x;
    for (int i=0;i<n;i++)
        v[i]=lower_bound(begin(x),end(x),V[i])-begin(x);
    string bits="";
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<lg;j++)
        {
            if ((1<<j)&v[i])
                bits+='1';
            else
                bits+='0';
        }
    }
    save_to_floppy(bits);
}

std::vector<int> solve_queries(int subtask_id, int n,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
    vector<int>ans;
    vector<int>arr;
    int lg=log2(n)+1;
    for (int i=0;i<n;i++)
    {
        arr.push_back(0);
        for (int j=0;j<lg;j++)
        {
            if (bits[lg*i+j]=='1')
                arr.back()+=(1<<j);
        }
    }
    for (int i=0;i<n;i++)
        mx[i][0]=arr[i];
    for (int i=1;(1<<i)<=n;i++)
        for (int j=0;j+(1<<i)-1<n;j++)
            mx[j][i]=max(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
    for (int i=0;i<a.size();i++)
    {
        int l,r;
        l=a[i],r=b[i];
        int mx=get(l,r);
        int st=l-1,en=r;
        while (st+1<en)
        {
            int mid=(st+en)/2;
            if (get(l,mid)==mx)
                en=mid;
            else
                st=mid;
        }
        ans.push_back(en);
    }
    return ans;
}

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