| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1301320 | mduchello | Bubble Sort 2 (JOI18_bubblesort2) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
//=====================================================================================================================================
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pii pair<int, int>
#define BIT(i, mask) ((mask >> (i)) & 1)
#define DAOBIT(i, mask) ((mask ^ (1 << i)))
#define OFFBIT(i, mask) ((mask & ~(1 << (i))))
#define ONBIT(i, mask) ((mask | (1 << (i))))
#define nmax 1000007
//=====================================================================================================================================
const int N = 1e6 + 7;
const ll mod = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll inf = 1e18;
int n, q;
ll a[N];
int vt[N];
ll val[N];
//=====================================================================================================================================
void fre(){
freopen("LIBRARY.INP", "r", stdin);
freopen("LIBRARY.out", "w", stdout);
}
ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b){
return (a / gcd(a, b)) * b;
}
vector<pair<ll, pii>> b;
void roirac(){
sort(b.begin(), b.end());
int counter = 1;
if(b[0].se.se) a[b[0].se.fi] = 1;
else val[b[0].se.fi] = 1;
for(int i = 1; i < b.size(); i++){
if(b[i].fi != b[i - 1].fi) counter++;
if(b[i].se.se) a[b[i].se.fi] = counter;
else val[b[i].se.fi] = counter;
}
}
int b2[N];
void sub3(){
for(int k = 1; k <= q; k++){
a[vt[k]] = val[k];
for(int i = 1; i <= n; i++) b2[i] = a[i];
sort(b2 + 1, b2 + n + 1);
vector<queue<int>> mp(8007);
for(int i = 1; i <= n; i++){
mp[b2[i]].push(i);
}
int pass = 0;
for(int i = 1; i <= n; i++){
int correct_pos = mp[a[i]].front();
mp[a[i]].pop();
if(i > correct_pos){
pass = max(pass, i - correct_pos);
}
}
cout << pass << '\n';
}
}
//=====================================================================================================================================
int main(){
cin.tie(0)->sync_with_stdio(0);
// fre();
cin >> n >> q;
for(int i = 1; i <= n; i++){
cin >> a[i];
b.pb({a[i], {i, 1} });
}
for(int i = 1; i <= q; i++){
cin >> vt[i] >> val[i];
vt[i]++;
b.pb({val[i], {i, 0} });
}
roirac();
if(n <= 8e3 && q <= 8e3){
sub3();
return 0;
}
return 0;
}