답안 #478169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
478169	2021-10-06T07:34:41 Z	Tenis0206	Floppy (RMI20_floppy)	C++17	컴파일 오류	0 ms	0 KB

floppy

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

using namespace std;

struct RMQ
{
    int poz, val;
};

RMQ rmq[25][100005];
int l[100005],Log2[100005];

/*string string_de_biti;
void save_to_floppy(string bits)
{
    string_de_biti = bits;
}
*/

void read_array(int subtask_id, const vector<int> &v)
{
    int n = v.size();
    string bits;
    stack<int> st;
    for(int i=0;i<n;i++)
    {
        while(!st.empty() && v[st.top()]<v[i])
        {
            bits.push_back('0');
            st.pop();
        }
        st.push(i);
        bits.push_back('1');
    }
    while(!st.empty())
    {
        bits.push_back('0');
        st.pop();
    }
    save_to_floppy(bits);
}

RMQ get_min(RMQ x, RMQ y)
{
    if(x.val<y.val || (x.val==y.val && x.poz>y.poz))
    {
        return x;
    }
    return y;
}

void build_rmq(int n)
{
    for(int i=2;i<=n;i++)
    {
        Log2[i] = 1 + Log2[i/2];
    }
    for(int i=1;i<=n;i++)
    {
        rmq[0][i].poz = i;
        rmq[0][i].val = l[i];
    }
    for(int k=1;k<=Log2[n];k++)
    {
        for(int i=1;i<=n;i++)
        {
            rmq[k][i] = get_min(rmq[k-1][i],rmq[k-1][i+(1<<(k-1))]);
        }
    }
}

int query(int x, int y)
{
    int k = Log2[y-x+1];
    return get_min(rmq[k][x],rmq[k][y-(1<<k)+1]).poz;
}

vector<int> solve_queries(int subtask_id, const string &bits, const vector<int> &a, const vector<int> &b)
{
    int n = bits.size()/2;
    int poz = 0;
    stack<int> st;
    for(int i=1;i<=n;i++)
    {
        while(!st.empty() && bits[poz]=='0')
        {
            st.pop();
            ++poz;
        }
        if(st.empty())
        {
            l[i] = 0;
        }
        else
        {
            l[i] = st.top();
        }
        st.push(i);
        ++poz;
    }
    build_rmq(n);
    vector<int> rez;
    for(int i=0;i<a.size();i++)
    {
        rez.push_back(query(a[i]+1,b[i]+1)-1);
    }
    return rez;
}

/*int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<int> v;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        v.push_back(x);
    }
    vector<int> a,b;
    for(int i=1;i<=m;i++)
    {
        int st,dr;
        cin>>st>>dr;
        a.push_back(st);
        b.push_back(dr);
    }
    read_array(1,v);
    vector<int> abcd = solve_queries(1,string_de_biti,a,b);
    for(auto it : abcd)
    {
        cout<<it<<'\n';
    }
    return 0;
}
*/

Compilation message

floppy.cpp: In function 'std::vector<int> solve_queries(int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~
/usr/bin/ld: /tmp/ccV1nLXe.o: in function `run2()':
stub.cpp:(.text+0x698): undefined reference to `solve_queries(int, int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, std::vector<int, std::allocator<int> > const&, std::vector<int, std::allocator<int> > const&)'
collect2: error: ld returned 1 exit status