| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1301322 | mduchello | Bubble Sort 2 (JOI18_bubblesort2) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define nmax 100007
int n, q;
int a[nmax];
int b2[nmax];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int k = 1; k <= q; k++) {
int pos, val;
cin >> pos >> val;
pos++; // nếu input 0-based, nếu 1-based thì bỏ dòng này
a[pos] = val; // update giá trị tại vị trí pos
// tính số pass Bubble Sort sau update
for(int i = 1; i <= n; i++) b2[i] = a[i];
sort(b2 + 1, b2 + n + 1);
vector<queue<int>> mp(8007); // giả sử giá trị a[i] <= 8000
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'; // in kết quả ngay lập tức
}
return 0;
}