#include <stdlib.h>
#include <string.h>
#include <bits/stdc++.h>
#include "floppy.h"
using namespace std;
int v2[40005],n;
stack <int> st;
void read_array(int subtask_id, const std::vector<int> &x) {
std::string bits;
n=x.size();
int i;
for (i=1;i<=n;i++)
{
v2[i]=x[i-1];
}
for (i=1;i<=n;i++)
{
while (!st.empty()&&v2[st.top()]<v2[i])
{
st.pop();
bits+="1";
}
st.push(i);
bits+="0";
}
save_to_floppy(bits);
}
int stanga[50005];
vector <pair <int,int> > queryuri;
pair <int,int> arb[160005];
void update(int st,int dr,int nod,int poz,int val)
{
if (st==dr)
{
arb[nod].first=val;
arb[nod].second=poz;
return;
}
int mij=(st+dr)/2;
if (poz<=mij)
{
update(st,mij,2*nod,poz,val);
}
else
{
update(mij+1,dr,2*nod+1,poz,val);
}
if (arb[2*nod].first<arb[2*nod+1].first)
{
arb[nod]=arb[2*nod];
}
else
{
arb[nod]=arb[2*nod+1];
}
}
pair <int,int> query(int st,int dr,int nod,int ua,int ub)
{
if (ua<=st&&dr<=ub)
{
return arb[nod];
}
int mij=(st+dr)/2; pair <int,int> r1={1e9,0},r2={1e9,0};
if (ua<=mij)
{
r1=query(st,mij,2*nod,ua,ub);
}
if (mij<ub)
{
r2=query(mij+1,dr,2*nod+1,ua,ub);
}
if (r1.first<r2.first)
{
return r1;
}
return r2;
}
std::vector<int> solve_queries(int subtask_id, int N,
const std::string &bits,
const std::vector<int> &a, const std::vector<int> &b) {
n=N;
int i,poz;
while (!st.empty())st.pop();
poz=1;
for (i=0;i<bits.size();i++)
{
if (bits[i]=='0')
{
if (st.empty())
{
stanga[poz]=0;
}
else
{
stanga[poz]=st.top();
}
st.push(poz);
poz++;
}
else
{
st.pop();
}
}
for (i=1;i<=n;i++)
{
update(1,n,1,i,stanga[i]);
}
for (i=0;i<a.size();i++)
{
queryuri.push_back({a[i]+1,b[i]+1});
}
vector <int> answers;
for (i=0;i<queryuri.size();i++)
{
answers.push_back(query(1,n,1,queryuri[i].first,queryuri[i].second).second-1);
}
return answers;
}
Compilation message
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:86:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (i=0;i<bits.size();i++)
| ~^~~~~~~~~~~~
floppy.cpp:110:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (i=0;i<a.size();i++)
| ~^~~~~~~~~
floppy.cpp:115:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (i=0;i<queryuri.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) {
| ~~~~~~~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
772 KB |
Output is correct |
| 2 |
Correct |
2 ms |
768 KB |
Output is correct |
| 3 |
Correct |
2 ms |
776 KB |
Output is correct |
| 4 |
Correct |
2 ms |
772 KB |
Output is correct |
| 5 |
Correct |
2 ms |
764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
3040 KB |
Output is correct |
| 2 |
Correct |
31 ms |
2956 KB |
Output is correct |
| 3 |
Correct |
28 ms |
2952 KB |
Output is correct |
| 4 |
Correct |
32 ms |
3032 KB |
Output is correct |
| 5 |
Correct |
32 ms |
3192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
10140 KB |
Output is correct |
| 2 |
Correct |
129 ms |
10220 KB |
Output is correct |
| 3 |
Correct |
122 ms |
10216 KB |
Output is correct |
| 4 |
Correct |
132 ms |
13772 KB |
Output is correct |
| 5 |
Correct |
129 ms |
13756 KB |
Output is correct |
