| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1301337 | mduchello | Bubble Sort 2 (JOI18_bubblesort2) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define nmax 1000007
typedef long long ll;
typedef pair<int,int> pii;
int n, q;
ll a[nmax];
int vt[nmax];
ll val[nmax];
// Compression vector
vector<pair<ll, pii>> b;
// Rời rạc hóa giá trị
void roirac() {
sort(b.begin(), b.end());
int counter = 1;
if(b[0].second.second) a[b[0].second.first] = 1;
else val[b[0].second.first] = 1;
for(int i = 1; i < b.size(); i++) {
if(b[i].first != b[i-1].first) counter++;
if(b[i].second.second) a[b[i].second.first] = counter;
else val[b[i].second.first] = counter;
}
}
// Tính số lần pass sau mỗi query (chỉ áp dụng khi n, q <= 8000)
vector<int> sub3() {
vector<int> res;
int b2[nmax];
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);
}
res.push_back(pass);
}
return res;
}
// Hàm countScans theo yêu cầu
vector<int> countScans(vector<ll>& A, vector<int>& X, vector<ll>& V) {
n = A.size();
q = X.size();
for(int i = 0; i < n; i++) {
a[i+1] = A[i];
b.push_back({A[i], {i+1, 1}});
}
for(int i = 0; i < q; i++) {
vt[i+1] = X[i]; // giả sử X[i] 0-based
val[i+1] = V[i];
b.push_back({V[i], {i+1, 0}});
}
roirac();
if(n <= 8000 && q <= 8000) return sub3();
}