#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "bubblesort2.h"
using namespace std;
mt19937 rnd(chrono :: steady_clock :: now().time_since_epoch().count());
struct Treap {
Treap *left = nullptr, *right = nullptr;
int x, y, p, val, ma, siz = 1, lazy = 0;
Treap (int _x = 0, int _p = 0, int _val = 0) : x(_x), y(rnd()), p(_p), val(_val), ma(_val) {};
void push() {
if (left != nullptr)
left -> lazy += lazy;
if (right != nullptr)
right -> lazy += lazy;
val += lazy;
ma += lazy;
lazy = 0;
}
void update() {
push();
if (left != nullptr)
left -> push();
if (right != nullptr)
right -> push();
ma = max({val, (left != nullptr ? left -> ma : val), (right != nullptr ? right -> ma : val)});
siz = (left != nullptr ? left -> siz : 0) + (right != nullptr ? right -> siz : 0) + 1;
}
};
int siz(Treap *t) {
return t == nullptr ? 0 : t -> siz;
}
Treap* Merge(Treap *t1, Treap *t2) {
if (t1 == nullptr)
return t2;
if (t2 == nullptr)
return t1;
t1 -> push();
t2 -> push();
if (t1 -> y > t2 -> y) {
t1 -> right = Merge(t1 -> right, t2);
t1 -> update();
return t1;
}
t2 -> left = Merge(t1, t2 -> left);
t2 -> update();
return t2;
}
pair <Treap*, Treap*> split(Treap *t, int x, int p) {
if (t == nullptr)
return {nullptr, nullptr};
t -> push();
if (t -> x > x || (t -> x == x && t -> p >= p)) {
auto a = split(t -> left, x, p);
t -> left = a.nd;
t -> update();
return {a.st, t};
}
auto a = split(t -> right, x, p);
t -> right = a.st;
t -> update();
return {t, a.nd};
}
void add(Treap *t, int val) {
if (t != nullptr)
t -> lazy += val;
}
Treap *root;
vector <int> countScans(vector <int> a, vector <int> x, vector <int> v){
int n = a.size(), q = x.size();
vector <II> b(n);
for (int i = 0; i < n; i ++)
b[i] = {a[i], i};
sort(b.begin(), b.end());
for (int i = 0; i < n; i ++)
root = Merge(root, new Treap(b[i].st, b[i].nd, b[i].nd - i));
vector <int> ans(q);
for (int t = 0; t < q; t ++) {
int pos = x[t], val = v[t];
if (val < a[pos]) {
auto za = split(root, val, pos), zb = split(za.nd, a[pos], pos), zc = split(zb.nd, a[pos], pos + 1);
add(zb.st, -1);
root = Merge(Merge(new Treap(val, pos, pos - siz(za.st)), za.st), Merge(zb.st, zc.nd));
}
else {
auto za = split(root, a[pos], pos), zc = split(za.nd, a[pos], pos + 1), zb = split(zc.nd, val, pos);
add(zb.st, 1);
root = Merge(Merge(new Treap(val, pos, pos - siz(za.st) - siz(zb.st)), za.st), Merge(zb.st, zb.nd));
}
a[pos] = val;
root -> push();
ans[t] = root -> ma;
}
return ans;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:88:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
88 | for (int i = 0; i < n; i ++)
| ^~~
bubblesort2.cpp:90:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
90 | vector <int> ans(q);
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
