Submission #398501

#	Time	Username	Problem	Language	Result	Execution time	Memory
398501		model_code	Floppy (RMI20_floppy)	C++17	100 / 100	115 ms	17888 KiB

floppy

/**
* user:  arapi-bcd
* fname: Taulant
* lname: Arapi
* task:  Floppy
* score: 100.0
* date:  2020-12-03 11:34:28.846634
*/
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#include "floppy.h"

vector<vector<int>> sp;
vector<int> w;

void init_rangemax(const vector<int> &v){
 w = v;
 int n = v.size();
 int log = 0;
 for(int i=1; i<n; i *= 2) ++log;
 sp.resize(log+1, vector<int>(n));
 iota(sp[0].begin(), sp[0].end(), 0);
 for(int i=1; i<=log; ++i){
  for(int j=0; j+(1<<i)<=n; ++j){
   sp[i][j]=sp[i-1][j];
   if(w[sp[i-1][j+(1<<(i-1))]] > w[sp[i][j]]) sp[i][j] = sp[i-1][j+(1<<(i-1))];
  }
 }
}

int rangemax(int l, int r){
 int len = r-l+1;
 int log = 0;
 while((1 << (log+1))<=len) ++log;
 int ret = sp[log][l];
 if(w[ret] < w[sp[log][r-(1 << log)+1]]) ret = sp[log][r-(1 << log)+1];
 return ret;
}

void read_array(int subtask_id, const vector<int> &v){
 int n = v.size();
 string tree(2*n, '0');
 int i;
 init_rangemax(v);
 queue<pii> q;
 q.push({0,n-1});
 while(!q.empty()){
  pii p = q.front(); q.pop();
  int l = p.first, r = p.second;
  int m = rangemax(l, r);
  if(m > l){
   tree[2*i]='1';
   q.push({l, m-1});
  }
  if(m < r){
   tree[2*i+1]='1';
   q.push({m+1, r});
  }
  ++i;
 }
 save_to_floppy(tree);
}

vector<int> solve_queries(int subtask_id, int n, const string &bits, const vector<int> &a, const vector<int> &b){
 vector<int> w(n);
 vector<int> l(n, -1), r(n, -1), siz(n, 1), up(n), pos(n);
 int j = 1;
 for(int i=0; i<n; ++i){
  if(bits[2*i] == '1') l[i] = j++;
  if(bits[2*i+1] == '1') r[i] = j++;
 }
 for(int i=n-1; i>=0; --i){
  if(l[i] >= 0) siz[i] += siz[l[i]];
  if(r[i] >= 0) siz[i] += siz[r[i]];
 }
 for(int i=0; i<n; ++i){
  pos[i] = up[i];
  if(l[i] >= 0) pos[i] += siz[l[i]], up[l[i]]=up[i];
  if(r[i] >= 0) up[r[i]]=pos[i]+1;
 }
 w[0]=n;
 for(int i=0; i<n; ++i){
  if(l[i] >= 0) w[pos[l[i]]] = w[pos[i]]-1;
  if(r[i] >= 0) w[pos[r[i]]] = w[pos[i]]-1;
 }
 init_rangemax(w);
 vector<int> ans(a.size());
 for(int i=0; i<a.size(); ++i) ans[i] = rangemax(a[i], b[i]);
 return ans;
}

Compilation message (stderr)

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:89:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(int i=0; i<a.size(); ++i) ans[i] = rangemax(a[i], b[i]);
      |               ~^~~~~~~~~
floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:44:6: warning: 'i' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |  int i;
      |      ^

• Subtask 1: 7 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72