#include <bits/stdc++.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 'void read_array(int, const std::vector<int>&)':
floppy.cpp:40:5: error: 'save_to_floppy' was not declared in this scope
40 | save_to_floppy(bits);
| ^~~~~~~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | 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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
