oj.uz

Submission #746307

# Submission time Handle Problem Language Result Execution time Memory
746307 2023-05-22T09:28:25 Z doowey Floppy (RMI20_floppy) C++14
100 / 100
 968 ms 12204 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 672 KB Output is correct
2 Correct 2 ms 672 KB Output is correct
3 Correct 2 ms 672 KB Output is correct
4 Correct 2 ms 684 KB Output is correct
5 Correct 2 ms 656 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3172 KB Output is correct
2 Correct 44 ms 3176 KB Output is correct
3 Correct 66 ms 3216 KB Output is correct
4 Correct 77 ms 3140 KB Output is correct
5 Correct 46 ms 3240 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 11596 KB Output is correct
2 Correct 451 ms 11648 KB Output is correct
3 Correct 787 ms 12204 KB Output is correct
4 Correct 968 ms 12048 KB Output is correct
5 Correct 459 ms 11640 KB Output is correct