Submission #494466

#	Time	Username	Problem	Language	Result	Execution time	Memory
494466		boykut	Floppy (RMI20_floppy)	C++14	18.45 / 100	47 ms	3740 KiB

floppy

#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 (stderr)

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 / 7
• Subtask 2: 11.4516836994 / 21
• Subtask 3: 0 / 72