Submission #1261853

#TimeUsernameProblemLanguageResultExecution timeMemory
1261853g4yuhgBubble Sort 2 (JOI18_bubblesort2)C++20
100 / 100
1529 ms167644 KiB
//Huyduocdithitp #include <bits/stdc++.h> #include "bubblesort2.h" typedef int ll; #define pii pair<ll, ll> #define MP make_pair #define fi first #define se second #define TASK "mansion" #define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);} #define faster ios_base::sync_with_stdio(false);cin.tie(NULL); #define N 500005 #define M 1000006 #define LOG 18 #define endl '\n' using namespace std; bool ghuy4g; ll S; ll n, q, a[N], m, st[6 * M], f[6 * M]; pii qr[N]; vector<pii> ns; set<ll> s[2000006]; ll bit[M * 2]; void upd(ll u, ll v) { ll idx = u; while (idx <= m) { bit[idx] += v; idx += idx & (-idx); } } ll get(ll u) { ll idx = u, ans = 0; while (idx > 0) { ans += bit[idx]; idx -= idx & (-idx); } return ans; } ll gm(ll id) { if (s[id].size() == 0) return 0; else return *s[id].rbegin(); } void build(ll id, ll l, ll r) { if (l == r) { st[id] = gm(l) - 1 - get(l - 1); return; } ll mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); st[id] = max(st[id * 2], st[id * 2 + 1]); } void pre() { sort(ns.begin(), ns.end()); ns.resize(unique(ns.begin(), ns.end()) - ns.begin()); m = ns.size(); for (int i = 1; i <= n; i ++) { a[i] = lower_bound(ns.begin(), ns.end(), make_pair(a[i], i)) - ns.begin() + 1; upd(a[i], 1); //cout << a[i] << " "; s[a[i]].insert(i); } //cout << endl; for (int i = 1; i <= q; i ++) { qr[i].se = lower_bound(ns.begin(), ns.end(), make_pair(qr[i].se, qr[i].fi)) - ns.begin() + 1; //cout << qr[i].fi << " " << qr[i].se << endl; } build(1, 1, m); } void lazy(ll id) { if (f[id] == 0) return; st[id] += f[id]; if (id * 2 < 4 * N) { f[id * 2] += f[id]; } if (id * 2 + 1 < 4 * N) { f[id * 2 + 1] += f[id]; } f[id] = 0; } void update(ll id, ll l, ll r, ll L, ll R, ll v) { lazy(id); if (l > R || r < L) return; if (L <= l && r <= R) { f[id] += v; lazy(id); return; } ll mid = (l + r) / 2; update(id * 2, l, mid, L, R, v); update(id * 2 + 1, mid + 1, r, L, R, v); st[id] = max(st[id * 2], st[id * 2 + 1]); } void update1(ll id, ll l, ll r, ll i, ll v) { lazy(id); if (i > r || i < l || l > r) return; if (l == r) { st[id] = v; return; } ll mid = (l + r) / 2; update1(id * 2, l, mid, i, v); update1(id * 2 + 1, mid + 1, r, i, v); st[id] = max(st[id * 2], st[id * 2 + 1]); } vector<int> answer; void solve() { for (int id = 1; id <= q; id ++) { ll i = qr[id].fi, v = qr[id].se; ll o_v = a[i], n_v = v; a[i] = n_v; if (o_v == n_v) { //cout << max(0, st[1]) << endl; answer.push_back(max(0, st[1])); continue; } //cout << i << " " << o_v << " " << n_v << endl; upd(o_v, -1); upd(n_v, 1); s[o_v].erase(i); update1(1, 1, m, o_v, gm(o_v) - get(o_v - 1) - 1); s[n_v].insert(i); update1(1, 1, m, n_v, gm(n_v) - get(n_v - 1) - 1); if (o_v < n_v) { // o_v + 1 -> n_v - 1 update(1, 1, m, o_v + 1, n_v - 1, 1); } else { update(1, 1, m, n_v + 1, o_v - 1, -1); } //cout << max(0, st[1]) << endl; answer.push_back(max(0, st[1])); } } vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) { //cin >> n >> q; n = A.size(), q = X.size(); for (int i = 1; i <= n; i ++) { //cin >> a[i]; a[i] = A[i - 1]; ns.push_back({a[i], i}); } for (int i = 1; i <= q; i ++) { //cin >> qr[i].fi >> qr[i].se; qr[i].fi = X[i - 1]; qr[i].se = V[i - 1]; qr[i].fi ++ ; //cout << qr[i].fi << " | " << qr[i].se << endl; ns.push_back({qr[i].se, qr[i].fi}); } pre(); solve(); return answer; } bool klinh; /*signed main(void) { faster; //countScans(); cerr << fabs(&klinh - &ghuy4g) / 1048576.0; return 0; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...