Submission #494339

#	Time	Username	Problem	Language	Result	Execution time	Memory
494339		boris_mihov	Floppy (RMI20_floppy)	C++14	100 / 100	101 ms	22940 KiB

floppy

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

using namespace std;
const int maxn = 1e5+10, maxlog = 20;

int sparse[maxlog][2*maxn], n;
int get_log[maxn];
int parent[maxn];
vector < int > g[maxn], a;

string s;

int cmp(int x, int y) {
 
    if (a[x] > a[y]) return x;
    return y;

}

int find_max(int l, int r) {

    int log = get_log[r-l+1];
    return cmp(sparse[log][l], sparse[log][r - (1 << log) + 1]);

}

int cnt;
void dfs(int l, int r) {

    if (cnt >= n+5) return;
    int mid = find_max(l, r)+1;
    
    s[2*cnt] = s[2*cnt+1] = '1'; 
    if (mid == l) s[2*cnt] = '0';
    if (mid == r) s[2*cnt+1] = '0';
    

    if (mid != l) {
    
        ++cnt;
        dfs(l, mid-1);
    
    }

    if (mid != r) {
        
        ++cnt;
        dfs(mid+1, r);
    
    }

}

void read_array(int subtask_id, const vector < int > &v) {
    
    a = v;

    // build_sparse
    n = v.size();

    for (int i = 1 ; i <= n ; ++i)
        sparse[0][i] = i-1;

    for (int log = 1 ; (1 << log) <= n ; ++log)
        for (int i = 1 ; i + (1 << log) - 1 <= n ; ++i)
            sparse[log][i] = cmp(sparse[log-1][i], sparse[log-1][i + (1 << log-1)]);

    for (int i = 1 ; i <= n ; ++i) {

        get_log[i] = get_log[i-1];
        if ((1 << get_log[i]+1) < i) ++get_log[i];

    }

    cnt = 0;
    s.resize(2*n-2);
    cnt = 0;
    dfs(1, n);

    save_to_floppy(s);

}

int pos[maxn], from_pos[maxn], in[maxn];
int subtree_size[maxn];
int depth[maxn];
vector < int > tour;

int cmp2(int x, int y) {

    if (depth[x] < depth[y]) return x;
    return y;

}

void dfs2(int parent, int addpos) {

    sparse[0][cnt] = parent;
    subtree_size[cnt] = 1;
    depth[cnt] = depth[parent]+1;
    tour.push_back(cnt);
    in[cnt] = tour.size()-1;

    int curr = cnt;
    if (s[2*curr] == '1') {

        int next = ++cnt; 
        dfs2(curr, addpos);
        tour.push_back(curr);
        subtree_size[curr] += subtree_size[next];

    }

    pos[curr] = subtree_size[curr] + addpos;
    from_pos[pos[curr]] = curr;

    if (s[2*curr+1] == '1') {

        int next = ++cnt; 
        dfs2(curr, pos[curr]);
        tour.push_back(curr);
        subtree_size[curr] += subtree_size[next];

    }

}

int query(int l, int r) {

    int log = get_log[r-l+1];
    return cmp2(sparse[log][l], sparse[log][r - (1 << log) + 1]);

}

vector< int > solve_queries(int subtask_id, int N, const string &bits, const vector < int > &a, const vector < int > &b) {

    s = bits;
    cnt = 0;
    dfs2(0, 0);

    vector < int > ans;

    for (int i = 0 ; i < tour.size() ; ++i)
        sparse[0][i] = tour[i];

    for (int log = 1 ; (1 << log) <= tour.size() ; ++log)
        for (int i = 0 ; i + (1 << log) - 1 < tour.size() ; ++i)
            sparse[log][i] = cmp2(sparse[log-1][i], sparse[log-1][i + (1 << log-1)]);

    for (int i = 1 ; i <= tour.size() ; ++i) {

        get_log[i] = get_log[i-1];
        if ((1 << get_log[i]+1) < i) ++get_log[i];

    }

    for (int i = 0 ; i < a.size() ; ++i) {
        
        ans.push_back(pos[query(in[from_pos[a[i]+1]], in[from_pos[b[i]+1]])]-1);

    }

    return ans;

}

/*
3 4 9
40 20 30 10
0 3 0
0 1 0
2 3 2
1 3 2
1 2 2
2 3 2
1 1 1
3 3 3
0 2 0

3 4 1
40 20 30 10
1 1 1
*/

Compilation message (stderr)

floppy.cpp: In function 'void read_array(int, const std::vector<int>&)':
floppy.cpp:69:79: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   69 |             sparse[log][i] = cmp(sparse[log-1][i], sparse[log-1][i + (1 << log-1)]);
      |                                                                            ~~~^~
floppy.cpp:74:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   74 |         if ((1 << get_log[i]+1) < i) ++get_log[i];
      |                   ~~~~~~~~~~^~
floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:146:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (int i = 0 ; i < tour.size() ; ++i)
      |                      ~~^~~~~~~~~~~~~
floppy.cpp:149:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for (int log = 1 ; (1 << log) <= tour.size() ; ++log)
      |                        ~~~~~~~~~~~^~~~~~~~~~~~~~
floppy.cpp:150:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for (int i = 0 ; i + (1 << log) - 1 < tour.size() ; ++i)
      |                          ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
floppy.cpp:151:80: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  151 |             sparse[log][i] = cmp2(sparse[log-1][i], sparse[log-1][i + (1 << log-1)]);
      |                                                                             ~~~^~
floppy.cpp:153:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int i = 1 ; i <= tour.size() ; ++i) {
      |                      ~~^~~~~~~~~~~~~~
floppy.cpp:156:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  156 |         if ((1 << get_log[i]+1) < i) ++get_log[i];
      |                   ~~~~~~~~~~^~
floppy.cpp:160:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     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 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72