| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 129503 | godwind | Bubble Sort 2 (JOI18_bubblesort2) | C++14 | 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.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
using namespace std;
template<typename T> void uin(T &a, T b) {
if (b < a) {
a = b;
}
}
template<typename T> void uax(T &a, T b) {
if (b > a) {
a = b;
}
}
#define ghost signed
#define left left228
#define right right228
#define prev prev228
#define list list228
const int N = 1000 * 1000 + 228;
const int INF = 1e9 + 228;
namespace FF
{
int t[N];
int n;
int res = 0;
void inc(int i, int x) {
--i;
for (; i < n; i |= (i + 1)) t[i] += x;
}
int getr(int i) {
--i;
res = 0;
for (; i >= 0; i = (i & (i + 1)) - 1) res += t[i];
return res;
}
int get(int l, int r) {
return getr(r) - getr(l - 1);
}
};
struct node
{
int mx, mod;
int l, r;
node() {
mx = mod = l = r = 0;
}
};
node d[3 * N];
void build(int l, int r, int v = 1) {
d[v].l = l;
d[v].r = r;
d[v].mx = -INF;
if (l == r) return;
int m = (l + r) >> 1;
build(l, m, v << 1);
build(m + 1, r, v << 1 | 1);
}
int gets(int v) {
return d[v].mx + d[v].mod;
}
void push(int v) {
d[v << 1].mod += d[v].mod;
d[v << 1 | 1].mod += d[v].mod;
d[v].mod = 0;
d[v].mx = max(gets(v << 1), gets(v << 1 | 1));
}
void update(int l, int r, int x, int v = 1) {
if (d[v].l > r || d[v].r < l) return;
if (l <= d[v].l && d[v].r <= r) {
d[v].mod += x;
} else {
push(v);
update(l, r, x, v << 1);
update(l, r, x, v << 1 | 1);
d[v].mx = max(gets(v << 1), gets(v << 1 | 1));
}
}
void SET(int pos, int value, int v = 1) {
if (d[v].l == d[v].r) {
d[v].mod = 0;
d[v].mx = value;
} else {
int m = (d[v].l + d[v].r) >> 1;
push(v);
if (pos <= m) SET(pos, value, v << 1);
else SET(pos, value, v << 1 | 1);
d[v].mx = max(gets(v << 1), gets(v << 1 | 1));
}
}
int get_max() {
return gets(1);
}
int get(int l, int r, int v = 1) {
if (l > r || d[v].l > r || d[v].r < l) return -INF;
if (l <= d[v].l && d[v].r <= r) return gets(v);
push(v);
return max(get(l, r, v << 1), get(l, r, v << 1 | 1));
}
int a[N], p[N];
int kek[N], POS[N], VAL[N];
ghost main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
vector< pair<int, int> > crd;
for (int i = 1; i <= n; ++i) {
crd.emplace_back(a[i], i);
}
sort(crd.begin(), crd.end());
for (int i = 1; i <= n; ++i) {
p[i] = lower_bound(crd.begin(), crd.end(), make_pair(a[i], i)) - crd.begin() + 1;
}
for (int i = 1; i <= n; ++i) kek[i] = i - p[i];
for (int i = 1; i <= m; ++i) {
cin >> POS[i] >> VAL[i];
crd.emplace_back(VAL[i], POS[i] + 1);
}
sort(crd.begin(), crd.end());
int sz = (int)crd.size();
FF::n = sz;
build(1, sz);
/*init*/
for (int i = 1; i <= n; ++i) {
int pos = lower_bound(crd.begin(), crd.end(), make_pair(a[i], i)) - crd.begin() + 1;
FF::inc(pos, 1);
SET(pos, kek[i]);
}
/*init*/
int pos, val;
for (int iter = 0; iter < m; ++iter) {
pos = POS[iter + 1], val = VAL[iter + 1];
++pos;
int was = lower_bound(crd.begin(), crd.end(), make_pair(a[pos], pos)) - crd.begin() + 1;
FF::inc(was, -1);
SET(was, -INF);
update(was + 1, sz, 1);
a[pos] = val;
int bec = lower_bound(crd.begin(), crd.end(), make_pair(a[pos], pos)) - crd.begin() + 1;
FF::inc(bec, 1);
update(bec + 1, sz, -1);
SET(bec, pos - FF::getr(bec - 1) - 1);
cout << get_max() << '\n';
}
return 0;
} // kek ;