oj.uz

Submission #474469

# Submission time Handle Problem Language Result Execution time Memory
474469 2021-09-18T11:41:54 Z Alexandruabcde Floppy (RMI20_floppy) C++14
100 / 100
 104 ms 15760 KB 
#include <stdlib.h>
#include <string.h>

#include "floppy.h"
#include <iostream>

std::vector <std::vector <int> > RMQ;
std::vector <int> Log;
std::vector <int> arr;
std::string floppy;

void Precompute_RMQ (std::vector<int> v) {
    Log.resize(v.size()+1);
    arr.resize(v.size());
    for (int i = 0; i < v.size(); ++ i )
        arr[i] = v[i];

    Log[1] = 0;
    for (int i = 2; i <= v.size(); ++ i )
        Log[i] = Log[i/2] + 1;

    RMQ.resize(Log[v.size()]+1);
    RMQ[0].resize(v.size());

    for (int i = 0; i < v.size(); ++ i )
        RMQ[0][i] = i;

    for (int lg = 1; lg <= Log[v.size()]; ++ lg ) {
        RMQ[lg].resize(v.size());
        for (int i = 0; i + (1<<lg) - 1 < v.size(); ++ i )  {
            int poz_st = RMQ[lg-1][i];
            int poz_dr = RMQ[lg-1][i+(1<<(lg-1))];

            if (arr[poz_st] > arr[poz_dr]) RMQ[lg][i] = poz_st;
            else RMQ[lg][i] = poz_dr;
        }
    }
}

int Answer_RMQ (int L, int R) {
    int k = Log[R-L+1];

    int poz_st = RMQ[k][L];
    int poz_dr = RMQ[k][R-(1<<k)+1];

    if (arr[poz_st] > arr[poz_dr]) return poz_st;
    else return poz_dr;
}

void DFS (int L, int R) {
    if (L > R) return;
    int position = Answer_RMQ(L, R);

    if (position == L) floppy.push_back('0');
    else floppy.push_back('1');
    if (position == R) floppy.push_back('0');
    else floppy.push_back('1');

    DFS(L, position-1);
    DFS(position+1, R);
}

void read_array(int subtask_id, const std::vector<int> &v) {
    Precompute_RMQ(v);
    DFS(0, v.size()-1);
    arr.clear();
    RMQ.clear();
    Log.clear();
    save_to_floppy(floppy);
}

int global_index = 0;
int position = 0;

void FindArray (int depth = 1) {
    char st = floppy[global_index*2];
    char dr = floppy[global_index*2+1];

    if (st == '1') {
        global_index++;
        FindArray(depth+1);
    }
    arr[position] = depth;
    ++ position;
    if (dr == '1') {
        global_index++;
        FindArray(depth+1);
    }
}

void Precompute_NEW_RMQ () {
    Log.resize(arr.size()+1);
    Log[1] = 0;
    for (int i = 2; i <= arr.size(); ++ i )
        Log[i] = Log[i/2] + 1;

    RMQ.resize(Log[arr.size()]+1);
    for (int i = 0; i <= Log[arr.size()]; ++ i )
        RMQ[i].resize(arr.size());
    for (int i = 0; i < arr.size(); ++ i )
        RMQ[0][i] = i;

    for (int lg = 1; lg <= Log[arr.size()]; ++ lg )
        for (int i = 0; i + (1<<lg) - 1 < arr.size(); ++ i ) {
            int poz_st = RMQ[lg-1][i];
            int poz_dr = RMQ[lg-1][i+(1<<(lg-1))];

            if (arr[poz_st] < arr[poz_dr]) RMQ[lg][i] = poz_st;
            else RMQ[lg][i] = poz_dr;
        }
}

int Answer_NEW_RMQ (int L, int R) {
    int k = Log[R-L+1];
    int poz_st = RMQ[k][L];
    int poz_dr = RMQ[k][R-(1<<k)+1];

    if (arr[poz_st] < arr[poz_dr]) return poz_st;
    else return poz_dr;
}

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b) {
    std::vector<int> ans;
    floppy = bits;

    arr.resize(floppy.size()/2);
    FindArray(0);
    Precompute_NEW_RMQ();

    for (int i = 0; i < a.size(); ++ i )
        ans.push_back(Answer_NEW_RMQ(a[i], b[i]));

    return ans;
}

Compilation message

floppy.cpp: In function 'void Precompute_RMQ(std::vector<int>)':
floppy.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i = 0; i < v.size(); ++ i )
      |                     ~~^~~~~~~~~~
floppy.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 2; i <= v.size(); ++ i )
      |                     ~~^~~~~~~~~~~
floppy.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0; i < v.size(); ++ i )
      |                     ~~^~~~~~~~~~
floppy.cpp:30:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i = 0; i + (1<<lg) - 1 < v.size(); ++ i )  {
      |                         ~~~~~~~~~~~~~~~~^~~~~~~~~~
floppy.cpp: In function 'void Precompute_NEW_RMQ()':
floppy.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 2; i <= arr.size(); ++ i )
      |                     ~~^~~~~~~~~~~~~
floppy.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i = 0; i < arr.size(); ++ i )
      |                     ~~^~~~~~~~~~~~
floppy.cpp:104:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for (int i = 0; i + (1<<lg) - 1 < arr.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:130:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     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 772 KB Output is correct
3 Correct 2 ms 784 KB Output is correct
4 Correct 3 ms 796 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 26 ms 4556 KB Output is correct
2 Correct 26 ms 4464 KB Output is correct
3 Correct 26 ms 4408 KB Output is correct
4 Correct 26 ms 4716 KB Output is correct
5 Correct 26 ms 4480 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 15200 KB Output is correct
2 Correct 104 ms 15148 KB Output is correct
3 Correct 101 ms 15124 KB Output is correct
4 Correct 102 ms 15760 KB Output is correct
5 Correct 104 ms 15316 KB Output is correct