| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 835216 | jmyszka2007 | 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>
#include <fstream>
using namespace std;
template<class A, class B>
ostream& operator<<(ostream& o, const pair<A, B>& p) {return o << '(' << p.first << ", " << p.second << ')';}
template<size_t Index = 0, typename... Types>
ostream& printTupleElements(ostream& o, const tuple<Types...>& t) {if constexpr (Index < sizeof...(Types)){if(Index > 0){o << ", ";}o << get<Index>(t);printTupleElements<Index + 1>(o, t);}return o;}
template<typename... Types>
ostream& operator<<(ostream& o, const tuple<Types...>& t){o << "(";printTupleElements(o, t);return o << ")";}
template<class T>
auto operator<<(ostream& o, const T& x) -> decltype(x.end(), o){o << '{';bool first = true;for (const auto& e : x){if (!first){o << ", ";}o << e;first = false;} return o << '}';}
//#define DEBUG
#ifdef DEBUG
#define fastio()
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'
#define check(x) if (!(x)) { cerr << "Check failed: " << #x << " in line " << __LINE__ << endl; exit(1); }
#else
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0);
#define debug(...)
#define check(x)
#endif
typedef long long ll;
#define pi pair<int, int>
#define pl pair<ll, ll>
#define st first
#define nd second
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
constexpr int base = (1 << 20);
int tri[2 * base];
int lazy[2 * base];
int nr[2 * base];
int nr2[2 * base];
void spl(int v) {
tri[2 * v] += lazy[v];
tri[2 * v + 1] += lazy[v];
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
lazy[v] = 0;
}
void upd(int v, int l, int r, int a, int b, int x) {
if(b < l || r < a) {
return;
}
if(a <= l && r <= b) {
tri[v] += x;
lazy[v] += x;
return;
}
spl(v);
int mid = (l + r) / 2;
upd(2 * v, l, mid, a, b, x);
upd(2 * v + 1, mid + 1, r, a, b, x);
tri[v] = max(tri[2 * v], tri[2 * v + 1]);
}
int que(int v, int l, int r, int a, int b) {
if(b < l || r < a) {
return 0;
}
if(a <= l && r <= b) {
return tri[v];
}
spl(v);
int mid = (l + r) / 2;
int ans = 0;
ans = max(ans, que(2 * v, l, mid, a, b));
ans = max(ans, que(2 * v + 1, mid + 1, r, a, b));
tri[v] = max(tri[2 * v], tri[2 * v + 1]);
return ans;
}
void solve() {
//ifstream cin("nazwa.in");
//ofstream cout("nazwa.out");
int n, t;
cin >> n >> t;
vector<tuple<int, int, int> >evs;
for(int i = 0; i < n; i++) {
int x;
cin >> x;
evs.eb(x, i, 0);
}
vector<pi>zap;
for(int i = 1; i <= t; i++) {
int a, b;
cin >> a >> b;
evs.eb(b, a, i);
zap.eb(a, b);
}
sort(all(evs));
debug(evs);
for(int i = 0; i < 2 * base; i++) {
tri[i] = -1e9;
}
int k = 0;
for(auto [a, b, i] : evs) {
if(i) {
nr[i] = k++;
}
else {
nr2[b] = k++;
}
}
vi pop(n);
vi val(n);
for(int i = 0; i < n; i++) {
val[i] = 1e9 + i;
upd(1, 0, base - 1, nr2[i], nr2[i], val[i]);
upd(1, 0, base - 1, nr2[i] + 1, k, -1);
debug(nr2[i], nr2[i]);
pop[i] = nr2[i];
}
for(int i = 1; i <= t; i++) {
auto [a, b] = zap[i - 1];
upd(1, 0, base - 1, pop[a], pop[a], -val[a]);
upd(1, 0, base - 1, pop[a] + 1, k, 1);
pop[a] = nr[i];
upd(1, 0, base - 1, pop[a], pop[a], val[a]);
upd(1, 0, base - 1, pop[a] + 1, k, -1);
cout << que(1, 0, base - 1, 0, k) << '\n';
}
}
int main() {
fastio();
int t;
//cin >> t;
t = 1;
while(t--) {
solve();
}
}