#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
struct dor {
dor *l, *r;
int dt, sh;
dor() {
l = r = NULL;
dt = sh = 0;
}
int sd() {
return dt + sh;
}
void sheps() {
if(l == NULL) l = new dor();
if(r == NULL) r = new dor();
l->sh += sh;
r->sh += sh;
sh = 0;
}
void pump() {
dt = max(l->sd(), r->sd());
}
} *rt = new dor();
void gnk(int l, int r, int sl, int sr, int vl, dor *&t) {
if(l > sr || r < sl) return;
if(l >= sl && r <= sr) {
t->sh += vl;
return;
}
t->sheps();
gnk(l, (l + r) / 2, sl, sr, vl, t->l);
gnk((l + r) / 2 + 1, r, sl, sr, vl, t->r);
t->pump();
}
const int inf = 1000000000;
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
int n = a.size();
int q = x.size();
vector<int> fp;
vector<pair<int, int> > u;
map<pair<int, int>, int> ma;
for(int i = 0; i < n; ++i) {
u.push_back({a[i], i});
}
for(int i = 0; i < q; ++i) {
u.push_back({v[i], x[i]});
}
sort(u.begin(), u.end());
for(int i = 0; i < n + q; ++i) {
ma[u[i]] = i + 1;
}
for(int i = 0; i < n; ++i) {
int rae = ma[{a[i], i}];
gnk(1, n + q, rae, rae, i, rt);
gnk(1, n + q, rae + 1, n + q, -1, rt);
}
int rvu;
for(int i = 0; i < q; ++i) {
int sdn = ma[{a[x[i]], x[i]}], sad = ma[{v[i], x[i]}];
rvu = 1;
a[x[i]] = v[i];
if(sdn > sad) swap(sdn, sad), rvu = -1;
gnk(1, n + q, sdn, sdn, -inf, rt);
if(sad - sdn >= 2) gnk(1, n + q, sdn + 1, sad - 1, rvu, rt);
gnk(1, n + q, sad, sad, inf + v[i], rt);
int tp = rt->sd();
fp.push_back(tp);
}
return fp;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
4596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
