Submission #899955

# Submission time Handle Problem Language Result Execution time Memory
899955 2024-01-07T10:51:31 Z Cookie Floppy (RMI20_floppy) C++14
100 / 100
79 ms 22604 KB
#include<bits/stdc++.h>
#include<fstream>
#include "floppy.h"
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const int mxn = 40069;
string val = "";
int idnode = 1, idval = 0;
int adj[mxn + 1][2], tin[mxn + 1], tt = 0, tonode[mxn + 1], up[mxn + 1][16], dep[mxn + 1];
void dfs(int s){
    if(val[idval] == '1'){
        adj[s][0] = ++idnode; idval++; dep[adj[s][0]] = dep[s] + 1;
        dfs(adj[s][0]);  up[adj[s][0]][0] = s;
    }else idval++;
    tin[s] = tt; tonode[tt++] = s;
    if(val[idval] == '1'){
        adj[s][1] = ++idnode; idval++; dep[adj[s][1]] = dep[s] + 1;
        dfs(adj[s][1]);  up[adj[s][1]][0] = s;
    }else idval++;
}
int lca(int u, int v){
    if(dep[u] < dep[v])swap(u, v);
    int k = dep[u] - dep[v];
    forr(i, 0, 16){
        if(k & (1 << i))u = up[u][i];
    }
    if(u == v)return(u);
    dorr(i, 15, 0){
        if(up[u][i] != up[v][i]){
            u = up[u][i]; v = up[v][i];
        }
    }
    return(up[u][0]);
}
std::vector<int> solve_queries(int subtask_id, int N,
        const std::string &bits,
        const std::vector<int> &a, const std::vector<int> &b) {
    val = bits;
    dfs(1);
    for(int i = 1; (1 << i) <= idnode; i++){
        for(int j = 1; j <= idnode; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    for(int i = 1; i <= idnode; i++){
        //cout << tin[i] << ' ';
        //if(adj[i][0])cout << adj[i][0] << " ";
        //if(adj[i][1])cout << adj[i][1] << " ";
        //cout << "\n";
    }
    vt<int>answers;
    for(int i = 0; i < sz(a); i++){
        int u = tonode[a[i]], v = tonode[b[i]];
        //cout << u << " " << v << "\n";
        answers.pb(tin[lca(u, v)]);
    }
    //for(auto i: answers)cout << i << " ";
    return answers;
}
 
pii mx[mxn + 1][16];
 
bool lson[mxn + 1], rson[mxn + 1];
pii getmx(int l, int r){
    int lg = __lg(r - l + 1);
    return(max(mx[l][lg], mx[r - (1 << lg) + 1][lg]));
}
string ans = "";
void build(int l, int r){
    int id = getmx(l, r).se;
    if(id != l){
        ans += '1';
        lson[id] = 1;
        build(l, id - 1);
    }else ans += '0';
    if(id != r){
        ans += '1';
        rson[id] = 1;
        build(id + 1, r);
    }else{
        ans += '0';
    }
}
void read_array(int subtask_id, const std::vector<int> &v) {
    for(int i = 0; i < sz(v); i++)mx[i][0] = mpp(v[i], i);
    for(int i = 1; i < 16; i++){
        for(int j = 0; j + (1 << i) - 1 < sz(v); j++){
            mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]);
        }
    }
    build(0, sz(v) - 1);

    save_to_floppy(ans);
}

Compilation message

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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 2868 KB Output is correct
2 Correct 2 ms 2880 KB Output is correct
3 Correct 2 ms 2872 KB Output is correct
4 Correct 2 ms 2872 KB Output is correct
5 Correct 2 ms 2872 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 18 ms 8120 KB Output is correct
2 Correct 22 ms 8276 KB Output is correct
3 Correct 19 ms 8276 KB Output is correct
4 Correct 19 ms 8492 KB Output is correct
5 Correct 18 ms 8128 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 71 ms 21328 KB Output is correct
2 Correct 72 ms 21628 KB Output is correct
3 Correct 79 ms 22604 KB Output is correct
4 Correct 77 ms 22192 KB Output is correct
5 Correct 72 ms 21412 KB Output is correct