#include <bits/stdc++.h>
#include "bubblesort2.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e6 + 10, inf = 1e9, inff = 1e7;
int t[4 * MAXN], add[4 * MAXN], m;
vector <set<int>> s;
void build(int v, int tl, int tr) {
add[v] = inf;
t[v] = 0;
if (tl == tr)
return;
int tm = (tl + tr)>>1;
build((v << 1), tl, tm);
build(((v << 1)|1), tm + 1, tr);
}
void push(int v, int tl, int tr) {
if (tl == tr || add[v] == inf)
return;
t[(v << 1)] += add[v];
t[((v << 1)|1)] += add[v];
if (add[(v << 1)] == inf)
add[(v << 1)] = add[v];
else
add[(v << 1)] += add[v];
if (add[((v << 1)|1)] == inf)
add[((v << 1)|1)] = add[v];
else
add[((v << 1)|1)] += add[v];
add[v] = inf;
}
void upd(int v, int tl, int tr, int l, int r, int val) {
if (r < tl || tr < l)
return;
if (l <= tl && tr <= r) {
t[v] += val;
if (add[v] == inf)
add[v] = val;
else
add[v] += val;
return;
}
int tm = (tl + tr)>>1;
push(v, tl, tr);
upd((v << 1), tl, tm, l, r, val);
upd(((v << 1)|1), tm + 1, tr, l, r, val);
t[v] = max(t[(v << 1)], t[((v << 1)|1)]);
}
int get(int v, int tl, int tr, int l, int r) {
if (r < tl || tr < l)
return -inff;
push(v, tl, tr);
if (l <= tl && tr <= r)
return t[v];
int tm = (tl + tr)>>1;
return max(get((v << 1), tl, tm, l, r), get(((v << 1)|1), tm + 1, tr, l, r));
}
void addd(int i, int x) {
int mx1 = -*s[x].begin();
s[x].insert(-i);
int mx2 = -*s[x].begin();
upd(1, 0, m - 1, x, x, -mx1 + mx2);
upd(1, 0, m - 1, x + 1, m - 1, -1);
}
void del(int i, int x) {
int mx1 = -*s[x].begin();
s[x].erase(-i);
int mx2 = -*s[x].begin();
upd(1, 0, m - 1, x, x, -mx1 + mx2);
upd(1, 0, m - 1, x + 1, m - 1, 1);
}
vector <int> countScans(vector <int> a, vector <int> x, vector <int> v) {
int n = a.size(), q = x.size();
vector <int> ar = {};
for (int i = 0; i < n; i++) ar.pb(a[i]);
for (int i = 0; i < q; i++) ar.pb(v[i]);
sort(ar.begin(), ar.end());
m = unique(ar.begin(), ar.end()) - ar.begin();
for (int i = 0; i < n; i++)
a[i] = lower_bound(ar.begin(), ar.begin() + m, a[i]) - ar.begin();
for (int i = 0; i < q; i++)
v[i] = lower_bound(ar.begin(), ar.begin() + m, v[i]) - ar.begin();
build(1, 0, m - 1);
ar.clear();
for (int i = 0; i < n; i++) ar.pb(a[i]);
sort(ar.begin(), ar.end());
s.resize(m);
for (int i = 0; i < m; i++) {
s[i].clear();
s[i].insert(inff);
}
for (int i = 0; i < m; i++)
upd(1, 0, m - 1, i, i, -*s[i].begin());
for (int i = 0; i < n; i++)
addd(i, a[i]);
vector <int> ans;
for (int i = 0; i < q; i++) {
del(x[i], a[i]);
addd(x[i], v[i]);
a[x[i]] = v[i];
ans.pb(get(1, 0, m - 1, 0, m - 1));
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1024 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1024 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
2168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1024 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
