This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bubblesort2.h"
#include <algorithm>
#include <set>
using namespace std;
const int N = 1e6 + 2;
const int INF = 1 << 30;
int m;
int allValues[N];
set<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 cnt[id] = pos[sl].size(), node[id] = *prev(pos[sl].end()) - (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] = *prev(pos[sl].end()) - (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])].insert(i);
segtree.Build(0, 0, m - 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);
pos[old_idx].erase(X[i]);
int new_idx = GetIndex(V[i]);
segtree.Modify(old_idx, 1);
A[X[i]] = V[i];
pos[new_idx].insert(X[i]);
segtree.Modify(new_idx, -1);
answer[i] = segtree.GetMax();
}
return answer;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |