Submission #922720

#TimeUsernameProblemLanguageResultExecution timeMemory
922720daoquanglinh2007Floppy (RMI20_floppy)C++17
100 / 100
71 ms17960 KiB
#include <bits/stdc++.h> #include "floppy.h" using namespace std; #define isz(a) (int)(a).size() const int NM = 4e4, LOG = 15; int N, a[NM+5]; int f[LOG+5][NM+5]; string s; int ptr = 0, d[NM+5], sz[NM+5]; void build_sparse(){ for (int i = 1; i <= N; i++) f[0][i] = i; for (int i = 1; i <= LOG; i++) for (int j = 1; j+(1<<i)-1 <= N; j++){ int x = f[i-1][j], y = f[i-1][j+(1<<(i-1))]; if (a[x] > a[y]) f[i][j] = x; else f[i][j] = y; } } int get(int l, int r){ int i = __lg(r-l+1), x = f[i][l], y = f[i][r-(1<<i)+1]; if (a[x] > a[y]) return x; return y; } void dnc(int l, int r){ if (l > r) return; if (l == r){ s.push_back('0'); s.push_back('0'); return; } int mid = get(l, r); if (mid > l) s.push_back('1'); else s.push_back('0'); if (mid < r) s.push_back('1'); else s.push_back('0'); dnc(l, mid-1); dnc(mid+1, r); } void read_array(int subtask_id, const vector<int> &v) { N = isz(v); for (int i = 1; i <= N; i++) a[i] = v[i-1]; build_sparse(); dnc(1, N); save_to_floppy(s); } void dfs(int u){ sz[u] = 1; d[u] = 0; if (s[2*u] == '1'){ ptr += 2; int v = ptr/2; dfs(v); sz[u] += sz[v]; d[u] = max(d[u], d[v]+1); } if (s[2*u+1] == '1'){ ptr += 2; int v = ptr/2; dfs(v); sz[u] += sz[v]; d[u] = max(d[u], d[v]+1); } } void restore(int u, int l, int r){ int mid = (s[ptr] == '1' ? l+sz[u+1] : l); a[mid] = d[u]; if (s[2*u] == '1'){ ptr += 2; restore(ptr/2, l, mid-1); } if (s[2*u+1] == '1'){ ptr += 2; restore(ptr/2, mid+1, r); } } vector<int> solve_queries(int subtask_id, int _N, const string &bits, const vector<int> &l, const vector<int> &r) { s = bits; N = _N; dfs(0); ptr = 0; restore(0, 1, N); build_sparse(); vector <int> ans(isz(l)); for (int i = 0; i < isz(l); i++){ ans[i] = get(l[i]+1, r[i]+1)-1; } return ans; }

Compilation message (stderr)

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...