Submission #1092214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092214		De3b0o	Floppy (RMI20_floppy)	C++17	28 / 100	38 ms	8996 KiB

floppy

#include<bits/stdc++.h>
#include<random>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define ppb pop_back()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "Yes" << "\n";
#define no cout << "No" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
#include "floppy.h"

using namespace std;

pll seg[2000009];
ll aa[2000009];

void sb(ll x , ll l , ll r)
{
    if(l==r)
    {
        seg[x]={aa[l],l};
        return;
    }
    sb(lc,l,mid);
    sb(rc,mid+1,r);
    if(seg[lc].F>seg[rc].F)
        seg[x]=seg[lc];
    else
        seg[x]=seg[rc];
}

pll sg(ll x , ll l , ll r , ll l1 , ll r1)
{
    if(l>r1||r<l1)
        return {-1,-1};
    if(l>=l1&&r<=r1)
        return seg[x];
    pll sg1 = sg(lc,l,mid,l1,r1);
    pll sg2 = sg(rc,mid+1,r,l1,r1);
    if(sg1.F>sg2.F)
        return sg1;
    else
        return sg2;
}

void read_array(int subtask_id, const std::vector<int> &v)
{
    ll n = v.size();
    ll c = n;
    ll sz = 0;
    while(c)
    {
        c/=2;
        sz++;
    }
    map<ll,ll> mp;
    vector<int> vv = v;
    for(auto it : vv)
        mp[it]=1;
    c = 0;
    for(auto it : mp)
        mp[it.F]=c++;
    for(int i = 0 ; n>i ; i++)
        vv[i]=mp[v[i]];
    string s = "";
    for(int i = 0 ; n>i ; i++)
    {
        ll x = vv[i];
        string e = "";
        while(x)
        {
            if(x%2)
                e+='1';
            else
                e+='0';
            x/=2;
        }
        while(e.size()<sz)
            e+='0';
        s+=e;
    }
    save_to_floppy(s);
}

std::vector<int> solve_queries(int subtask_id, int N,const std::string &bits,const std::vector<int> &a, const std::vector<int> &b)
{
    ll n = N;
    ll c = n;
    ll sz = 0;
    while(c)
    {
        c/=2;
        sz++;
    }
    string s = bits;
    for(int i = 0 ; n>i ; i++)
    {
        ll b1 = 1;
        aa[i]=0;
        for(int j = i*sz ; (i+1)*sz>j ; j++)
        {
            if(bits[j]=='1')
                aa[i]+=b1;
            b1*=2;
        }
    }
    sb(1,0,n-1);
    vector<int> ans;
    for(int i = 0 ; a.size()>i ; i++)
    {
        pll sge = sg(1,0,n-1,a[i],b[i]);
        ans.pb(sge.S);
    }
    return ans;
}

Compilation message (stderr)

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:88:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   88 |         while(e.size()<sz)
      |               ~~~~~~~~^~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:119:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |     for(int i = 0 ; a.size()>i ; 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: 0 / 72