#include "bubblesort2.h"
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e6 + 2;
const int INF = 1 << 30;
int m;
int allValues[N];
priority_queue<int> pos[N];
struct TSegmentTree
{
#define lc id * 2 + 1
#define rc id * 2 + 2
#define mid (sl + sr) / 2
int node[1 << 21], lazy[1 << 21], cnt[1 << 21];
void Propagate(int id, int sl, int sr)
{
if (lazy[id] != 0)
{
node[id] += lazy[id];
if (sl < sr)
lazy[lc] += lazy[id], lazy[rc] += lazy[id];
lazy[id] = 0;
}
}
void Build(int id, int sl, int sr, int pref)
{
if (sl < sr)
{
Build(lc, sl, mid, pref);
Build(rc, mid + 1, sr, pref + cnt[lc]);
node[id] = max(node[lc], node[rc]);
cnt[id] = cnt[lc] + cnt[rc];
}
else
if (pos[sl].empty()) node[id] = -INF, cnt[id] = 0;
else node[id] = pos[sl].top() - pref, cnt[id] = 1;
}
void Modify(int id, int sl, int sr, int u, int val, int pref)
{
Propagate(id, sl, sr);
if (sl < sr)
{
if (u <= mid)
{
lazy[rc] += val;
Propagate(rc, mid + 1, sr);
Modify(lc, sl, mid, u, val, pref);
}
else
{
Propagate(lc, sl, mid);
Modify(rc, mid + 1, sr, u, val, pref + cnt[lc]);
}
node[id] = max(node[lc], node[rc]);
cnt[id] = cnt[lc] + cnt[rc];
}
else
if (pos[sl].empty()) cnt[id] = 0, node[id] = -INF;
else cnt[id] += -val, node[id] = pos[sl].top() - (pref + cnt[id]) + 1;
}
void Modify(int u, int val) { return Modify(0, 0, m - 1, u, val, 0); }
int GetMax() { return node[0]; }
#undef lc
#undef rc
#undef mid
} segtree;
int GetIndex(int x) { return lower_bound(allValues, allValues + m, x) - allValues; }
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
int n = A.size();
int q = X.size();
copy(A.begin(), A.end(), allValues);
copy(V.begin(), V.end(), allValues + n);
m = n + q;
sort(allValues, allValues + m);
m = unique(allValues, allValues + m) - allValues;
for (int i = 0; i < n; ++i)
pos[GetIndex(A[i])].push(i);
segtree.Build(0, 0, n - 1, 0);
vector<int> answer(q);
for (int i = 0; i < q; ++i)
{
int old_val = A[X[i]];
int old_idx = GetIndex(old_val);
A[X[i]] = V[i];
int new_idx = GetIndex(V[i]);
while (!pos[old_idx].empty() && A[pos[old_idx].top()] != old_val) pos[old_idx].pop();
segtree.Modify(old_idx, 1);
pos[new_idx].push(X[i]);
segtree.Modify(new_idx, -1);
answer[i] = segtree.GetMax();
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
31736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
31736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
32856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
31736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
