#include <bits/stdc++.h>
#include <bits/extc++.h>
#include "bubblesort2.h"
using namespace std;
using namespace __gnu_pbds;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> TREE;
namespace {
const int MXN = 500005;
int n;
vector<int> a;
TREE MS;
namespace TREAP {
mt19937 rnd(time(nullptr));
struct NODE {
int l, r, pri, sz, val, big, tag;
NODE(int v = 0) : l(0), r(0), pri(rnd()), sz(1), val(v), big(v), tag(0) {}
} nd[MXN];
int rt;
void add_tag(int id, int _t) {
if (id == 0) return;
nd[id].val += _t;
nd[id].big += _t;
nd[id].tag += _t;
}
void PUSH(int id) {
add_tag(nd[id].l, nd[id].tag);
add_tag(nd[id].r, nd[id].tag);
nd[id].tag = 0;
}
void PULL(int id) {
nd[id].big = max({nd[nd[id].l].big, nd[nd[id].r].big, nd[id].val});
nd[id].sz = nd[nd[id].l].sz + nd[nd[id].r].sz + 1;
}
int MERGE(int ta, int tb) {
if (ta == 0) return tb;
if (tb == 0) return ta;
if (nd[ta].pri > nd[tb].pri) {
PUSH(ta);
nd[ta].r = MERGE(nd[ta].r, tb);
PULL(ta);
return ta;
} else {
PUSH(tb);
nd[tb].l = MERGE(ta, nd[tb].l);
PULL(tb);
return tb;
}
return 0;
}
pii SPLIT(int rt, int k) {
if (k == 0) return mp(0, rt);
if (k == nd[rt].sz) return mp(rt, 0);
int lsz = nd[nd[rt].l].sz + 1;
PUSH(rt);
if (lsz <= k) {
auto [ta, tb] = SPLIT(nd[rt].r, k - lsz);
nd[rt].r = ta;
PULL(rt);
return mp(rt, tb);
} else {
auto [ta, tb] = SPLIT(nd[rt].l, k);
nd[rt].l = tb;
PULL(rt);
return mp(ta, rt);
}
return mp(0, 0);
}
}
void INIT() {
using namespace TREAP;
nd[0].sz = 0;
vector<pii> dist;
FOR(i, 0, n) dist.push_back(mp(a[i], i));
sort(dist.begin(), dist.end());
FOR(i, 0, n) MS.insert(dist[i]);
FOR(i, 0, n) {
nd[i + 1] = NODE(dist[i].sc - i);
}
rt = 1;
FOR(i, 1, n) rt = MERGE(rt, i + 1);
FOR(j, 1, n + 1) debug(j, nd[j]);
}
int SOLVE(int p, int v) {
using namespace TREAP;
int now = MS.order_of_key(mp(a[p], p));
MS.erase(MS.find(mp(a[p], p)));
int nxt = MS.order_of_key(mp(v, p));
MS.insert(mp(v, p));
a[p] = v;
debug(now, nxt);
if (now == nxt) return nd[rt].big;
auto [ta, t1] = SPLIT(rt, min(now, nxt));
auto [tt, td] = SPLIT(t1, abs(nxt - now) + 1);
if (now > nxt) {
auto [tb, tc] = SPLIT(tt, now - nxt);
debug(ta, tb, tc, td);
add_tag(tc, now - nxt);
add_tag(tb, -1);
tt = MERGE(tc, tb);
t1 = MERGE(tt, td);
rt = MERGE(ta, t1);
} else {
auto [tb, tc] = SPLIT(tt, 1);
debug(ta, tb, tc, td, 2);
add_tag(tb, now - nxt);
add_tag(tc, 1);
tt = MERGE(tc, tb);
t1 = MERGE(tt, td);
rt = MERGE(ta, t1);
}
return nd[rt].big;
}
}
ostream &operator<<(ostream &ss, TREAP::NODE a) {
ss << '<' << a.val << ' ' << a.big << ' ' << a.tag << ' ' << a.l << ' ' << a.r << '>';
return ss;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
::a = A;
::n = A.size();
int q = X.size();
vector<int> ans;
INIT();
FOR(i, 0, q) {
ans.push_back(SOLVE(X[i], V[i]));
using namespace TREAP;
FOR(j, 1, n + 1) debug(j, nd[j]);
}
for (auto &i : ans) assert(i >= 0);
return ans;
}
Compilation message
bubblesort2.cpp: In function 'void {anonymous}::INIT()':
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 39
| ^~
bubblesort2.cpp:105:20: note: in expansion of macro 'debug'
105 | FOR(j, 1, n + 1) debug(j, nd[j]);
| ^~~~~
bubblesort2.cpp: In function 'int {anonymous}::SOLVE(int, int)':
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 39
| ^~
bubblesort2.cpp:115:3: note: in expansion of macro 'debug'
115 | debug(now, nxt);
| ^~~~~
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 39
| ^~
bubblesort2.cpp:121:4: note: in expansion of macro 'debug'
121 | debug(ta, tb, tc, td);
| ^~~~~
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 39
| ^~
bubblesort2.cpp:129:4: note: in expansion of macro 'debug'
129 | debug(ta, tb, tc, td, 2);
| ^~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 39
| ^~
bubblesort2.cpp:154:20: note: in expansion of macro 'debug'
154 | FOR(j, 1, n + 1) debug(j, nd[j]);
| ^~~~~
bubblesort2.cpp: At global scope:
bubblesort2.cpp:140:10: warning: 'std::ostream& operator<<(std::ostream&, {anonymous}::TREAP::NODE)' defined but not used [-Wunused-function]
140 | ostream &operator<<(ostream &ss, TREAP::NODE a) {
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14064 KB |
Output is correct |
| 3 |
Correct |
11 ms |
14172 KB |
Output is correct |
| 4 |
Correct |
11 ms |
14172 KB |
Output is correct |
| 5 |
Incorrect |
11 ms |
14172 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14064 KB |
Output is correct |
| 3 |
Correct |
11 ms |
14172 KB |
Output is correct |
| 4 |
Correct |
11 ms |
14172 KB |
Output is correct |
| 5 |
Incorrect |
11 ms |
14172 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
16316 KB |
Output is correct |
| 2 |
Incorrect |
114 ms |
17768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14172 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14064 KB |
Output is correct |
| 3 |
Correct |
11 ms |
14172 KB |
Output is correct |
| 4 |
Correct |
11 ms |
14172 KB |
Output is correct |
| 5 |
Incorrect |
11 ms |
14172 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
