Submission #848895

#TimeUsernameProblemLanguageResultExecution timeMemory
848895TheSahibFloppy (RMI20_floppy)C++14
100 / 100
84 ms22680 KiB
#include <bits/stdc++.h> #include "floppy.h" using namespace std; const int MAX = 40005; const int LOGMAX = 16; pair<int, int> tree[MAX * 4]; int arr[MAX]; void build(int node, int l, int r){ if(l == r){ tree[node] = {arr[l], l}; return; } int mid = (l + r) / 2; build(node * 2, l, mid); build(node * 2 + 1, mid + 1, r); tree[node] = max(tree[node * 2], tree[node * 2 + 1]); } pair<int, int> ask(int node, int l, int r, int ql, int qr){ if(qr < l || ql > r) return {-1000, 0}; if(ql <= l && r <= qr){ return tree[node]; } int mid = (l + r) / 2; return max(ask(node * 2, l, mid, ql, qr), ask(node * 2 + 1, mid + 1, r, ql, qr)); } int n; string s; int nxt = 0; void dfs1(int l, int r){ pair<int, int> mx = ask(1, 0, n - 1, l, r); int id = nxt++; if(mx.second - 1 < l){ s[id * 2] = '0'; } else{ s[id * 2] = '1'; dfs1(l, mx.second - 1); } if(mx.second + 1 > r){ s[id * 2 + 1] = '0'; } else{ s[id * 2 + 1] = '1'; dfs1(mx.second + 1, r); } } void read_array(int subtask_id, const vector<int> &v) { n = v.size(); for (int i = 0; i < n; i++) { arr[i] = v[i] + 1000000001; } build(1, 0, n - 1); s.resize(n * 2); dfs1(0, n - 1); save_to_floppy(s); } int par[LOGMAX][MAX]; vector<int> g[MAX]; int nxtItr = 0; int dfs2(int itr){ int node1 = -1, node2 = -1; if(s[itr] == '1'){ nxtItr += 2; node1 = dfs2(nxtItr); } int node = nxt++; if(s[itr + 1] == '1'){ nxtItr += 2; node2 = dfs2(nxtItr); } if(node1 != -1){ par[0][node1] = node; g[node].push_back(node1); } if(node2 != -1){ par[0][node2] = node; g[node].push_back(node2); } return node; } int t = 0; int timeIn[MAX], timeOut[MAX]; void dfs3(int node){ timeIn[node] = ++t; for(int to:g[node]){ dfs3(to); } timeOut[node] = ++t; } bool isAncestor(int a, int b){ return timeIn[a] <= timeIn[b] && timeOut[a] >= timeOut[b]; } int lca(int a, int b){ if(isAncestor(a, b)) return a; if(isAncestor(b, a)) return b; for (int i = LOGMAX - 1; i >= 0; i--) { if(!isAncestor(par[i][a], b)){ a = par[i][a]; } } return par[0][a]; } std::vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) { n = N; nxt = 0; s = bits; int r = dfs2(0); par[0][r] = r; for (int j = 1; j < LOGMAX; j++) { for (int i = 0; i < n; i++) { par[j][i] = par[j - 1][par[j - 1][i]]; } } dfs3(r); vector<int> ans(a.size()); for (int i = 0; i < a.size(); i++) { ans[i] = lca(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:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     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) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...