oj.uz

Submission #478887

# Submission time Handle Problem Language Result Execution time Memory
478887 2021-10-08T19:37:50 Z Neacsu_Mihai Floppy (RMI20_floppy) C++14
100 / 100
 89 ms 14212 KB 
#include <iostream>
#include <stack>
#include <vector>
#include "floppy.h"

#define LOGMAX 17 //2 ^ 17 < NMAX, 2 ^ 18 > NMAX
#define NMAX 200000 //doua sute de mii

using namespace std;

int RMQ[LOGMAX + 1][NMAX + 1];
int stanga[NMAX + 1];
int log[NMAX + 1];

void read_array(int subtask_id, const vector<int> &v){
    int N = v.size();
    int k = 0;
    stack <int> st;
    string bits;

    for(int i = 0; i < N; 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 rezultant(int A, int B){
    if(stanga[A] < stanga[B]){
        return A;
    }
    else { //la egalitate il aleg pe B
        return B;
    }
}

void buildRMQ(int N){
    log[1] = 0;
    for(int j = 2; j <= N; j++){
        log[j] = log[j / 2] + 1;
    }

    for(int i = 1; i <= N; i++){
        RMQ[0][i] = i;
    }

    for(int j = 1; (1 << j) <= N; j++){
        for(int i = 1; i - 1 + (1 << j) <= N; i++){
            RMQ[j][i] = rezultant(RMQ[j - 1][i], RMQ[j - 1][i + (1 << (j - 1))]);
        }
    }
}

int query(int A, int B){
    //returnez minimul din [A, B]
    int k = log[B - A + 1];

    return rezultant(RMQ[k][A], RMQ[k][B - (1 << k) + 1]);
}

vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b){
    //dau build la stanga[]
    int poz = 0;
    stack <int> st;

    for(int i = 1; i <= n; i++){
        while(bits[poz] == '0'){
            st.pop();
            poz++;
        }

        //acum bits[poz] = 1
        if(st.empty()){
            stanga[i] = 0;
        }
        else {
            stanga[i] = st.top();
        }

        st.push(i);
        poz++;
    }

    buildRMQ(n);

    vector <int> rez;
    for(int i = 0; i < a.size(); i++){
        rez.push_back( query(a[i] + 1, b[i] + 1) - 1 );
    }
    return rez;
}

Compilation message

floppy.cpp:13:5: warning: built-in function 'log' declared as non-function [-Wbuiltin-declaration-mismatch]
   13 | int log[NMAX + 1];
      |     ^~~
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:17:9: warning: unused variable 'k' [-Wunused-variable]
   17 |     int k = 0;
      |         ^
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:95:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     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 780 KB Output is correct
2 Correct 2 ms 792 KB Output is correct
3 Correct 2 ms 792 KB Output is correct
4 Correct 2 ms 792 KB Output is correct
5 Correct 2 ms 780 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3824 KB Output is correct
2 Correct 21 ms 3840 KB Output is correct
3 Correct 21 ms 3764 KB Output is correct
4 Correct 22 ms 3856 KB Output is correct
5 Correct 23 ms 3848 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 14212 KB Output is correct
2 Correct 88 ms 14100 KB Output is correct
3 Correct 87 ms 14136 KB Output is correct
4 Correct 85 ms 14152 KB Output is correct
5 Correct 88 ms 14096 KB Output is correct