#include <bits/stdc++.h>
using namespace std;
#include "bubblesort2.h"
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();
}
int rwi(int l, int r, int si, dor *&t) {
if(l == r) return t->sd();
if((l + r) / 2 >= si) return rwi(l, (l + r) / 2, si, t->l);
return rwi((l + r) / 2 + 1, r, si, t->r);
}
const int inf = 100000000;
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) {
--x[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;
}
gnk(1, n + q, 1, n + q, -inf, rt);
for(int i = 0; i < n; ++i) {
int rae = ma[{a[i], i}];
gnk(1, n + q, rae, rae, inf + i, rt);
gnk(1, n + q, rae + 1, n + q, -1, rt);
}
int rvu;
//for(int j = 1; j <= n + q; ++j) cout << rwi(1, n + q, j, rt) << " ";
//cout << endl;
for(int i = 0; i < q; ++i) {
int sdn = ma[{a[x[i]], x[i]}], sad = ma[{v[i], x[i]}];
//cout << sdn << " " << sad << endl;
rvu = 1;
a[x[i]] = v[i];
gnk(1, n + q, sdn, sdn, -inf - x[i], rt);
gnk(1, n + q, sad, sad, inf + x[i], rt);
if(sdn > sad) swap(sdn, sad), rvu = -1;
//gnk(1, n + q, sdn, sdn, -inf - x[i], rt);
if(sad - sdn >= 2) gnk(1, n + q, sdn + 1, sad - 1, rvu, rt);
//gnk(1, n + q, sad, sad, inf + x[i], rt);
int tp = rt->sd();
fp.push_back(tp);
//for(int j = 1; j <= n + q; ++j) cout << rwi(1, n + q, j, rt) << " ";
//cout << endl;
}
return fp;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
4596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
