| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 884130 | vjudge1 | Bubble Sort 2 (JOI18_bubblesort2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "./bubblesort2.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <climits>
using namespace std;
namespace pbds = __gnu_pbds;
template<typename T>
using ordered_tree = pbds::tree<T, pbds::null_type, less<T>, pbds::rb_tree_tag, pbds::tree_order_statistics_node_update>;
using ipair = array<int, 2>;
constexpr int log2_ceil(int n) {
int i = 0;
while ((1 << i) < n) i++;
return i;
}
const int NMAX = 5e5;
class segment_tree { // poz = valoare, val.min = prima poz, val.max = ultima pozitie
struct interval {
int min = INT_MAX;
int max = INT_MIN;
};
int n;
vector<interval> aint;
int query_min(int b, int e, int i, int l, int r) {
if (l <= b && e <= r) return aint[i].min;
int m = (b + e) / 2;
if (r <= m) return query_min(b, m, i * 2 + 1, l, r);
if (l >= m + 1) return query_min(m + 1, e, i * 2 + 2, l, r);
return min(query_min(b, m, i * 2 + 1, l, r), query_min(m + 1, e, i * 2 + 2, l, r));
}
int query_max(int b, int e, int i, int l, int r) {
if (l <= b && e <= r) return aint[i].max;
int m = (b + e) / 2;
if (r <= m) return query_max(b, m, i * 2 + 1, l, r);
if (l >= m + 1) return query_max(m + 1, e, i * 2 + 2, l, r);
return max(query_max(b, m, i * 2 + 1, l, r), query_max(m + 1, e, i * 2 + 2, l, r));
}
void update(int b, int e, int i, int j, int v) {
if (b == e) {
aint[i].min = min(aint[i].min, v);
aint[i].max = max(aint[i].max, v);
return;
}
int m = (b + e) / 2;
if (j <= m) update(b, m, i * 2 + 1, j, v);
else update(m + 1, e, i * 2 + 2, j, v);
aint[i].min = min(aint[i * 2 + 1].min, aint[i * 2 + 1].min);
aint[i].max = max(aint[i * 2 + 1].max, aint[i * 2 + 1].max);
}
public:
int query_min(int l, int r) {
return query_min(0, n-1, 0, l, r);
}
int query_max(int l, int r) {
return query_max(0, n-1, 0, l, r);
}
void update(int j, int v) {
return update(0, n-1, 0, j, v);
}
int maxdiff(int j, int v) {
int ans1 = (j == 0 ? -1 : query_min(0, j-1) - query_max(j, j));
int ans2 = (j == n-1 ? -1 : query_max)
}
segment_tree(int _n) {
n = _n;
aint = vector<interval>(2 << log2_ceil(n));
}
};
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v){
int n = (int)a.size();
int q = (int)x.size();
vector<int> answer(q);
int diff_values = 0;
{
vector<int> s(n + q);
copy(a.begin(), a.end(), s.begin());
copy(v.begin(), v.end(), s.begin() + n);
sort(s.begin(), s.end());
s.resize(unique(s.begin(), s.end()) - s.begin());
for (int& k : a) k = lower_bound(s.begin(), s.end(), k) - s.begin();
for (int& k : v) k = lower_bound(s.begin(), s.end(), k) - s.begin();
diff_values = (int)s.size();
}
segment_tree aint(diff_values);
for (int i = 0; i < n; i++) {
aint.update(a[i], i);
}
multiset<int> maxes;
for (int i = 0; i < n; i++) {
maxes.insert(max())
}
for (int j = 0; j < q; j++) {
}
return answer;
}