oj.uz

Submission #639001

# Submission time Handle Problem Language Result Execution time Memory
639001 2022-09-08T07:31:39 Z ogibogi2004 Floppy (RMI20_floppy) C++14
100 / 100
 87 ms 14992 KB 
#include <stdlib.h>
#include <string.h>
#include<bits/stdc++.h>
#include "floppy.h"
using namespace std;
const int MAXN=4e4+6;

void read_array(int subtask_id, const vector<int> &v) {
    string bits="";
    stack<int>st;
    for(int i=0;i<v.size();i++)
    {
        while(!st.empty()&&v[st.top()]<v[i])
        {
            st.pop();
            bits+="0";
        }
        bits+="1";
        st.push(i);
    }
    save_to_floppy(bits);
}
int tl[MAXN];
int sp[MAXN][20];
vector<int> solve_queries(int subtask_id, int N,
        const string &bits,
        const vector<int> &a, const vector<int> &b) {
    int i=0;
    stack<int>st;
    vector<int>answers;
    //cout<<bits<<endl;
    for(int j=0;j<bits.size();j++)
    {
        if(bits[j]=='1')
        {
            if(!st.empty())tl[i]=st.top();
            else tl[i]=-1;
            st.push(i);
            i++;
        }
        else
        {
            st.pop();
        }
    }
    for(int i=0;i<N;i++)sp[i][0]=tl[i];
    for(int step=1;step<17;step++)
    {
        for(int i=0;i<N;i++)
        {
            if(sp[i][step-1]==-1)sp[i][step]=-1;
            else sp[i][step]=sp[sp[i][step-1]][step-1];
        }
    }
    //for(int i=0;i<N;i++)cout<<tl[i]<<" ";
    //cout<<endl;
    for(int i=0;i<b.size();i++)
    {
        int r=b[i];
        int l=a[i];
        for(int j=16;j>=0;j--)
        {
            if(sp[r][j]<l)continue;
            r=sp[r][j];
        }
        //cout<<r<<endl;
        answers.push_back(r);
    }
    return answers;
}

Compilation message

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     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:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int j=0;j<bits.size();j++)
      |                 ~^~~~~~~~~~~~
floppy.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0;i<b.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 796 KB Output is correct
2 Correct 2 ms 788 KB Output is correct
3 Correct 2 ms 800 KB Output is correct
4 Correct 2 ms 804 KB Output is correct
5 Correct 3 ms 804 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3288 KB Output is correct
2 Correct 26 ms 4172 KB Output is correct
3 Correct 20 ms 4108 KB Output is correct
4 Correct 20 ms 4192 KB Output is correct
5 Correct 20 ms 4004 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 11260 KB Output is correct
2 Correct 87 ms 14824 KB Output is correct
3 Correct 84 ms 14792 KB Output is correct
4 Correct 86 ms 14832 KB Output is correct
5 Correct 87 ms 14992 KB Output is correct