Submission #925323

#TimeUsernameProblemLanguageResultExecution timeMemory
925323boris_mihovBubble Sort 2 (JOI18_bubblesort2)C++17
17 / 100
9034 ms4444 KiB
#include "bubblesort2.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> #include <stack> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template <typename T> using OSet = tree <T, null_type, std::less <T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long llong; const int MAXN = 500000 + 10; const int INF = 1e9; int n, q; int in[MAXN]; int order[MAXN]; llong a[MAXN]; std::vector <int> countScans(std::vector <int> A, std::vector <int> X, std::vector <int> V) { n = A.size(); q = X.size(); for (int i = 1 ; i <= n ; ++i) { a[i] = A[i - 1]; } std::vector <int> answer(q, 0); for (int query = 0 ; query < q ; ++query) { OSet <llong> s; a[X[query] + 1] = V[query]; for (int i = 1 ; i <= n ; ++i) { answer[query] = std::max(answer[query], (int)s.size() - (int)s.order_of_key(n * a[i] + i)); s.insert(n * a[i] + i); } } return answer; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...