| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1095202 | haru09 | Bubble Sort 2 (JOI18_bubblesort2) | C++17 | 0 ms | 0 KiB |
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<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define task "code"
const int ar = 5e5 + 5;
const ll mod = 1e9 + 7;
int n, q;
int a[ar];
int pos[ar], x[ar];
vector<int> nen;
set<int> lis[ar * 2];
int st[(1 << 21) + 5];
int lz[(1 << 21) + 5];
void down(int id, int l, int r)
{
if (lz[id] == 0) return;
st[id] += lz[id];
if (l != r)
{
lz[id << 1] += lz[id];
lz[id << 1 | 1] += lz[id];
}
lz[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val)
{
if (u > v) return;
down(id, l, r);
if (l > v || r < u) return;
if (u <= l && r <= v)
{
lz[id] += val;
down(id, l, r);
return;
}
int mid = l + r >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
void update(int p, int add, int sub)
{
int id = 1;
int l = 1;
int r = nen.size() - 1;
while(l < r)
{
int mid = l + r >> 1;
down(id << 1, l, mid);
down(id << 1 | 1, mid + 1, r);
if (mid >= p)
{
id <<= 1;
r = mid;
}
else
{
id = id << 1 | 1;
l = mid + 1;
}
}
st[id] += add - sub;
while(id > 1)
{
id >>= 1;
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
nen.push_back(a[i]);
}
for (int i = 1; i <= q; i++)
{
cin >> pos[i] >> x[i];
pos[i]++;
nen.push_back(x[i]);
}
nen.push_back(0);
sort(nen.begin(), nen.end());
nen.erase(unique(nen.begin(), nen.end()), nen.end());
for (int i = 1; i < nen.size(); i++) lis[i].insert(0);
for (int i = 1; i <= n; i++)
{
a[i] = lower_bound(nen.begin(), nen.end(), a[i]) - nen.begin();
update(a[i], i, *lis[a[i]].rbegin());
lis[a[i]].insert(i);
update(1, 1, nen.size() - 1, a[i], nen.size() - 1, -1);
}
for (int i = 1; i <= q; i++)
{
x[i] = lower_bound(nen.begin(), nen.end(), x[i]) - nen.begin();
update(1, 1, nen.size() - 1, a[pos[i]], nen.size() - 1, 1);
update(1, 1, nen.size() - 1, x[i], nen.size() - 1, -1);
if (pos[i] == *lis[a[pos[i]]].rbegin())
{
update(a[pos[i]], *(--lis[a[pos[i]]].rbegin()), pos[i]);
}
if (pos[i] > *lis[x[i]].rbegin())
{
update(x[i], pos[i], *lis[x[i]].rbegin());
}
lis[a[pos[i]]].erase(pos[i]);
lis[x[i]].insert(pos[i]);
a[pos[i]] = x[i];
cout << st[1] << '\n';
}
}