# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
494455 | 2021-12-15T13:35:26 Z | iulia13 | Floppy (RMI20_floppy) | C++14 | 84 ms | 15644 KB |
#include <bits/stdc++.h> #include "floppy.h" using namespace std; const int N = 40005; const int LG = 20; int st[N]; int rmq[N][LG]; int lft[N]; ///void save_to_floppy(string &bits); void read_array(int subtask_id, const vector <int> &v) { string a = ""; int k = 0, n = v.size(); for (int i = 0; i < n; i++) { while (k && st[k] < v[i]) { a += '1'; k--; } st[++k] = v[i]; a += '0'; } save_to_floppy(a); } vector <int> sol; int lg[N]; vector<int> solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) { int k = 0, m = bits.size(), jj = 0; for (int i = 1; i <= N; i++) { if (1 < i) lg[i] = 1 + lg[i / 2]; while(k && bits[jj] == '1') k--, jj++; jj++; lft[i] = st[k]; st[++k] = i; rmq[i][0] = i; } for (int j = 1; (1 << j) <= N; j++) for (int i = 1; i <= N; i++) { rmq[i][j] = rmq[i][j - 1]; if (lft[rmq[i + (1 << (j - 1))][j - 1]] < i) rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1]; } int q = a.size(); for (int i = 0; i < q; i++) { int aa = a[i], bb = b[i]; aa++, bb++; int lgg = lg[bb - aa + 1]; int ans = rmq[aa][lgg]; if (lft[rmq[bb - (1 << lgg) + 1][lgg]] < aa) ans = rmq[bb - (1 << lgg) + 1][lgg]; sol.push_back(ans - 1); } return sol; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 776 KB | Output is correct |
2 | Correct | 2 ms | 764 KB | Output is correct |
3 | Correct | 2 ms | 764 KB | Output is correct |
4 | Correct | 2 ms | 776 KB | Output is correct |
5 | Correct | 3 ms | 764 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 3320 KB | Output is correct |
2 | Correct | 20 ms | 4036 KB | Output is correct |
3 | Correct | 19 ms | 4104 KB | Output is correct |
4 | Correct | 20 ms | 4120 KB | Output is correct |
5 | Correct | 22 ms | 4092 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 84 ms | 15644 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |