#include "bubblesort2.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 1e6 + 100;
struct seg{
vector <int> st, laz;
void ass(int n) {
st.assign(n * 4 + 100, 0);
laz.assign(n * 4 + 100, 0);
}
void push(int id) {
int t = laz[id];
laz[id * 2] += t;
laz[id * 2 + 1] += t;
st[id * 2] += t;
st[id * 2 + 1] += t;
laz[id] = 0;
}
void upd(int id, int l, int r, int u, int v, int c) {
if (l > v || r < u || u > v)
return;
if (l >= u && r <= v) {
st[id] += c;
laz[id] += c;
return;
}
push(id);
int m = (l + r) / 2;
upd(id * 2, l, m, u, v, c);
upd(id * 2 + 1, m + 1, r, u, v, c);
st[id] = max(st[id * 2], st[id * 2 + 1]);
}
int get() {
return st[1];
}
};
set <int> pos[N];
int a[N], used[N];
vector <int> countScans(vector <int> A, vector <int> X, vector <int> V) {
map <int, int> mp;
for (auto &x : A)
mp[x];
for (auto &x : V)
mp[x];
int sz = 0;
for (auto &x : mp) {
sz++;
x.s = sz;
}
seg st;
st.ass(sz);
int n = sz(A);
for (int i = 0; i < n; i++) {
A[i] = mp[A[i]];
a[i + 1] = A[i];
pos[a[i + 1]].insert(i + 1);
}
for (auto &x : V)
x = mp[x];
for (int i = n; i >= 1; i--) {
if (used[a[i]] == 0) {
used[a[i]] = 1;
st.upd(1, 1, sz, a[i], a[i], i);
}
st.upd(1, 1, sz, a[i], sz, -1);
}
vector <int> ans;
int q = sz(X);
for (int i = 0; i < q; i++) {
X[i]++;
int v = a[X[i]], nx = V[i];
st.upd(1, 1, sz, v, sz, 1);
st.upd(1, 1, sz, nx, sz, -1);
if (*(--pos[v].end()) == X[i]) {
if (sz(pos[v]) == 1) {
st.upd(1, 1, sz, v, v, -X[i]);
} else {
auto it = (--pos[v].end());
it--;
st.upd(1, 1, sz, v, v, -(X[i] - (*it)));
}
}
pos[v].erase(X[i]);
a[X[i]] = nx;
if (pos[nx].empty() || *(--pos[nx].end()) < X[i]) {
int add = X[i];
if (sz(pos[nx])) {
add -= *(--pos[nx].end());
}
st.upd(1, 1, sz, nx, nx, add);
}
pos[nx].insert(X[i]);
ans.pb(max(0, st.get() - 1));
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
51036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
51036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
52312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
51036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
