oj.uz

Submission #494466

# Submission time Handle Problem Language Result Execution time Memory
494466 2021-12-15T14:13:04 Z boykut Floppy (RMI20_floppy) C++14
18.4517 / 100
 47 ms 3740 KB 
#include <stdlib.h>
#include <string.h>
#include <bits/stdc++.h>

#include "floppy.h"

using namespace std;

void read_array(int subtask_id, const std::vector<int> &v) {
    vector<int> x;
    for (int i = 0; i < v.size(); i++) x.push_back(v[i]);
    sort(begin(x), end(x));
    x.erase(unique(begin(x), end(x)), end(x));
    vector<int> new_v(v.size());
    for (int i = 0; i < v.size(); i++) {
        new_v[i] = lower_bound(x.begin(), x.end(), v[i]) - x.begin();
    }

    std::string bits;
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < 16; j++) {
            if (new_v[i] & (1 << j)) bits += "1";
            else bits += "0";
        }
    }
    save_to_floppy(bits);
}

struct SegmentTreeMax {
   int n;
   vector<pair<int, int>> t;
   SegmentTreeMax(int n) : n(n), t((n << 2) + 1, {INT_MIN, INT_MIN}) {}
   void update(int i, int x, int v, int vl, int vr) {
      if (vl == vr) {
         t[v] = {x, vl};
      } else {
         int vm = (vl + vr) >> 1;
         if (i <= vm)
            update(i, x, v << 1, vl, vm);
         else
            update(i, x, v << 1 | 1, vm + 1, vr);
         t[v] = max(t[v << 1], t[v << 1 | 1]);
      }
   }
   pair<int, int> query(int l, int r, int v, int vl, int vr) {
      if (l > vr || vl > r) return {INT_MIN, INT_MIN};
      else if (l <= vl && vr <= r) return t[v];
      else {
         int vm = (vl + vr) >> 1;
         auto L = query(l, r, v << 1, vl, vm);
         auto R = query(l, r, v << 1 | 1, vm + 1, vr);
         return max(L, R);
      }
   }
   void update(int i, int x) {
      update(i, x, 1, 0, n - 1);
   }
   pair<int, int> query(int l, int r) {
      return query(l, r, 1, 0, n - 1);
   }
};

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;

    int M = a.size();
    SegmentTreeMax st(N);
    int j = 0;
    for (int i = 0; i < N; i++) {
        int cnt = 16, p = 1, sum = 0;
        while (cnt--) {
            if (bits[j] == '1') sum += p;
            p <<= 1;
            j++;
        }
        st.update(i, sum);
    }

    for (int i = 0; i < M; i++) {
        ans.push_back(st.query(a[i], b[i]).second);
    }

    return ans;
}

Compilation message

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:11:23: 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++) x.push_back(v[i]);
      |                     ~~^~~~~~~~~~
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:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < v.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 780 KB Output is correct
3 Correct 2 ms 780 KB Output is correct
4 Correct 4 ms 772 KB Output is correct
5 Correct 3 ms 764 KB Output is correct

Subtask #2
11.4516836994 / 21.0

# Verdict Execution time Memory Grader output
1 Partially correct 39 ms 3684 KB Partially correct
2 Partially correct 43 ms 3548 KB Partially correct
3 Partially correct 38 ms 3704 KB Partially correct
4 Partially correct 40 ms 3732 KB Partially correct
5 Partially correct 39 ms 3740 KB Partially correct

Subtask #3
0.0 / 72.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 2936 KB L is too large
2 Halted 0 ms 0 KB -