oj.uz

Submission #494335

# Submission time Handle Problem Language Result Execution time Memory
494335 2021-12-15T07:41:09 Z Tenis0206 Floppy (RMI20_floppy) C++17
100 / 100
 88 ms 14528 KB 
#include <bits/stdc++.h>
#include "floppy.h"

using namespace std;

/*string bglobal;

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

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

int rmq[25][100005];
int Log2[100005];

int l[100005];

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] = i;
    }
    for(int k=1;k<=Log2[n];k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(l[rmq[k-1][i]]<l[rmq[k-1][i+(1<<(k-1))]])
            {
                rmq[k][i] = rmq[k-1][i];
            }
            else
            {
                rmq[k][i] = rmq[k-1][i+(1<<(k-1))];
            }
        }
    }
}

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

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

/*int main()
{
    int n;
    cin>>n;
    vector<int> v;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        v.push_back(x);
    }
    int q;
    cin>>q;
    vector<int> a,b;
    for(int i=1;i<=q;i++)
    {
        int x,y;
        cin>>x>>y;
        a.push_back(x);
        b.push_back(y);
    }
    read_array(0,v);
    vector<int> rez = solve_queries(0,n,bglobal,a,b);
    for(auto it : rez)
    {
        cout<<it<<' ';
    }
    return 0;
}
*/

Compilation message

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         while(poz<bits.size() && bits[poz]=='0')
      |               ~~~^~~~~~~~~~~~
floppy.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 776 KB Output is correct
2 Correct 2 ms 792 KB Output is correct
3 Correct 2 ms 780 KB Output is correct
4 Correct 2 ms 792 KB Output is correct
5 Correct 2 ms 776 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3960 KB Output is correct
2 Correct 28 ms 4224 KB Output is correct
3 Correct 20 ms 3940 KB Output is correct
4 Correct 21 ms 3992 KB Output is correct
5 Correct 21 ms 4072 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 14352 KB Output is correct
2 Correct 76 ms 14416 KB Output is correct
3 Correct 88 ms 14376 KB Output is correct
4 Correct 87 ms 14528 KB Output is correct
5 Correct 75 ms 14516 KB Output is correct