oj.uz

Submission #805446

# Submission time Handle Problem Language Result Execution time Memory
805446 2023-08-03T16:42:58 Z Navas Floppy (RMI20_floppy) C++14
100 / 100
 881 ms 11900 KB 
#include <bits/stdc++.h>
#include "floppy.h"
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
#define fi first
#define se second
#define mp make_pair
 
void read_array(int subtask_id, const vector<int> &v) {
    string bits;
    vector<int> idx;
    for(int i = 0 ; i < v.size(); i ++ ){
        bits.push_back('1');
        while(!idx.empty() && v[idx.back()] < v[i]){
            bits.push_back('0');
            idx.pop_back();
        }
        idx.push_back(i);
    }
    save_to_floppy(bits);
}
 
vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b) {
    vector<int> answers = {};
    int p = 0;
    vector<int> L(n);
    vector<int> st;
    for(int i = 0 ; i < n; i ++ ){
        p ++ ;
        while(p < bits.size() && bits[p] == '0'){
            st.pop_back();
            p ++ ;
        }
        if(st.empty()) L[i] = -1;
        else L[i] = st.back();
        st.push_back(i);
    }
    int m = a.size();
    int big;
    for(int i = 0 ; i < m ; i ++ ){
        big = -1;
        for(int j = a[i]; j <= b[i]; j ++ ){
            if(L[j] < a[i]){
                big = j;
            }
        }
        answers.push_back(big);
    }
    return answers;
}

Compilation message

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     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:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while(p < bits.size() && bits[p] == '0'){
      |               ~~^~~~~~~~~~~~~
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 772 KB Output is correct
2 Correct 1 ms 672 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 2 ms 668 KB Output is correct
5 Correct 2 ms 700 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3140 KB Output is correct
2 Correct 38 ms 3196 KB Output is correct
3 Correct 67 ms 3244 KB Output is correct
4 Correct 66 ms 3108 KB Output is correct
5 Correct 39 ms 3228 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 9120 KB Output is correct
2 Correct 407 ms 11676 KB Output is correct
3 Correct 792 ms 11900 KB Output is correct
4 Correct 881 ms 11760 KB Output is correct
5 Correct 404 ms 11724 KB Output is correct