Submission #475271

#TimeUsernameProblemLanguageResultExecution timeMemory
475271stefantagaFloppy (RMI20_floppy)C++14
0 / 100
146 ms10176 KiB
#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].second) { 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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...