#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct treap {
treap *l = nullptr, *r = nullptr;
int x, y, siz = 1, p;
int c;
int lazy = 0;
int val;
void pushdown() {
if (l != nullptr) l -> lazy += lazy;
if (r != nullptr) r -> lazy += lazy;
val += lazy;
c += lazy;
lazy = 0;
}
void upd() {
pushdown();
siz = ((l == nullptr) ? 0 : l -> siz) + ((r == nullptr) ? 0 : r -> siz) + 1;
val = max(c, max((l == nullptr) ? 0 : l -> val, (r == nullptr) ? 0 : r -> val));
}
treap(int a, int pp, int cc) : x(a), y(rng()), p(pp), c(cc) {val = c;}
};
int siz(treap *t) { return (t == nullptr) ? 0 : t -> siz; }
treap *arr;
treap* merge(treap *t1, treap *t2) {
if (t1 == nullptr)
return t2;
if (t2 == nullptr)
return t1;
t1 -> pushdown();
t2 -> pushdown();
if (t1 -> y > t2 -> y) {
t1 -> r = merge(t1 -> r, t2);
t1 -> upd();
return t1;
} else {
t2 -> l = merge(t1, t2 -> l);
t2 -> upd();
return t2;
}
}
pair<treap*, treap*> split(treap *t, int x, int pos) {
if (t == nullptr)
return {nullptr, nullptr};
t -> pushdown();
if (t -> x > x || (t -> x == x && t -> p >= pos)) {
auto tmp = split(t -> l, x, pos);
t -> l = tmp.second;
t -> upd();
return {tmp.first, t};
} else {
auto tmp = split(t -> r, x, pos);
t -> r = tmp.first;
t -> upd();
return {t, tmp.second};
}
}
inline void addAll(treap *t, int a) { if (t != nullptr) t -> lazy += a; }
treap *root;
inline void ins(int a, int P, int c) {
pair<treap*, treap*> p = split(root, a, P);
root = merge(merge(p.fs, new treap(a, P, c)), p.sc);
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
int n = A.size();
pair<int, int> B[n];
for (int i = 0; i < n; i++)
B[i] = {A[i], i};
sort(B, B + n);
for (int i = 0; i < n; i++)
ins(B[i].fs, B[i].sc, B[i].sc - i);
vector<int> answer(X.size());
for (int query = 0; query < X.size(); query++) {
int pos = X[query], val = V[query];
if (A[pos] > val) {
//a.fs -end position of element- b.fs -this element- th.sc
auto a = split(root, val, pos);
auto b = split(a.sc, A[pos], pos);
auto th = split(b.sc, A[pos], pos + 1);
addAll(b.fs, -1);
root = merge(merge(a.fs, new treap(val, pos, pos - siz(a.fs))), merge(b.fs, th.sc));
} else {
//a.fs -this element- b.fs -end position of element- b.sc
auto a = split(root, A[pos], pos);
auto th = split(a.sc, A[pos], pos + 1);
auto b = split(th.sc, val, pos);
addAll(b.fs, 1);
root = merge(merge(a.fs, b.fs), merge(new treap(val, pos, pos - siz(a.fs) - siz(b.fs)), b.sc));
}
A[pos] = val;
answer[query] = root -> val;
}
return answer;
}
/* 1 2
4 2
1 2 3 4
0 3
2 1
*/
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:91:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int query = 0; query < X.size(); query++) {
~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
2816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
