oj.uz

Submission #398501

# Submission time Handle Problem Language Result Execution time Memory
398501 2021-05-04T12:04:27 Z model_code Floppy (RMI20_floppy) C++17
100 / 100
 115 ms 17888 KB 
/**
* 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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 776 KB Output is correct
2 Correct 3 ms 764 KB Output is correct
3 Correct 2 ms 772 KB Output is correct
4 Correct 2 ms 772 KB Output is correct
5 Correct 2 ms 764 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4540 KB Output is correct
2 Correct 26 ms 4592 KB Output is correct
3 Correct 31 ms 4544 KB Output is correct
4 Correct 30 ms 4608 KB Output is correct
5 Correct 27 ms 4644 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 15100 KB Output is correct
2 Correct 109 ms 17796 KB Output is correct
3 Correct 115 ms 17812 KB Output is correct
4 Correct 109 ms 17888 KB Output is correct
5 Correct 111 ms 17804 KB Output is correct