# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
996649 | 2024-06-11T03:31:43 Z | berWoW | Tree Rotations (POI11_rot) | C++17 | 36 ms | 65536 KB |
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> // namespace __gnu_pbds typedef __gnu_pbds::tree< int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set; #define MAX_N 212345 int n, cnt; int inv[4 * MAX_N]; ordered_set trunks[4 * MAX_N]; //void read_trunk(int u) { // int p; // scanf("%d", &p); // // if (p != 0) { trunks[u].insert(p); return; } // // read_trunk(2 * u), read_trunk(2 * u + 1); //} void count_inv(int u) { int p; scanf("%d", &p); if (p != 0) { trunks[u].insert(p); return; } int l = cnt++; count_inv(l); int r = cnt++; count_inv(r); if (trunks[l].size() < trunks[r].size()) trunks[l].swap(trunks[r]); int inv_l_r = 0, inv_r_l = 0; int i = 0; for (auto it = trunks[r].begin(); it != trunks[r].end(); it++) { trunks[l].insert(*it); int pos = trunks[l].order_of_key(*it); inv_l_r += trunks[l].size() - pos - 1; inv_r_l += pos - i++; } inv[u] = inv[l] + inv[r] + min(inv_l_r, inv_r_l); trunks[u].swap(trunks[l]); } int main() { scanf("%d", &n); //read_trunk(1); count_inv(cnt++); printf("%d\n", inv[0]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 31 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 30 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 33 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 28 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 30 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 36 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 29 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 31 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 32 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 30 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 28 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |