# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
248912 | 2020-07-13T17:55:30 Z | kostia244 | Ancient Books (IOI17_books) | C++17 | 1 ms | 384 KB |
#include "books.h" #include<bits/extc++.h> using namespace std; const int maxn = 1<<20; using ll = long long; using namespace __gnu_pbds; using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; ll vis[maxn][4]; ll minimum_walk(vector<int> p, int s) { oset pref, suf; vector<int> pos(p.size()); ll ans = 0, lst = -1; for(int i = 0; i < p.size(); i++) suf.insert(i), pos[p[i]] = i; for(int t, i = 0; i < p.size(); i++) { //cout << i << "::\n"; int v = p[i]; suf.erase(v); if(i != v) { vis[i][(v > i)*3]++; vis[i][1 + (pos[i]>i)]++; } t = pref.size()-pref.order_of_key(i+1); vis[i][1] += t, vis[i][3] += t; t = suf.order_of_key(i); vis[i][0] += t, vis[i][2] += t; pref.insert(v); if(vis[i][0] + vis[i][2]) lst = i; //for(int j = 0; j < 4; j++) cout << vis[i][j] << " "; cout << endl; if(i) { assert(vis[i][0] == vis[i-1][2]); assert(vis[i][1] == vis[i-1][3]); } } for(int i = 0; i <= lst; i++) { if(!(vis[i][0]+vis[i][2])) { vis[i][0] = vis[i][1] = vis[i][2] = vis[i][3] = 1; if(i) { vis[i-1][3]++; vis[i-1][2]++; } vis[i+1][0]++; vis[i+1][1]++; } } for(int i = 0; i < p.size(); i++) { vis[i][2] = vis[i][3] = max(vis[i][2], vis[i][3]); vis[i][0] = vis[i][1] = max(vis[i][0], vis[i][1]); ans += (vis[i][0] + vis[i][2]); } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 256 KB | 3rd lines differ - on the 1st token, expected: '6', found: '7' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 256 KB | 3rd lines differ - on the 1st token, expected: '6', found: '7' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 256 KB | 3rd lines differ - on the 1st token, expected: '6', found: '7' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 384 KB | 3rd lines differ - on the 1st token, expected: '3304', found: '2744' |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 256 KB | 3rd lines differ - on the 1st token, expected: '6', found: '7' |
2 | Halted | 0 ms | 0 KB | - |