Submission #1012323

#TimeUsernameProblemLanguageResultExecution timeMemory
1012323d4xnBubble Sort 2 (JOI18_bubblesort2)C++17
0 / 100
33 ms48208 KiB
#pragma GCC optimize ("Ofast") #include "bubblesort2.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() const int N = 5e5, inf = 1e9; int n, q, a[N], x[N], v[N], seg[2][N*8], laz[N*8]; vector<int> b, ans; vector<pair<int, int>> comp; void pushDown(int p) { for (int h : {p*2, p*2+1}) { seg[0][h] += laz[p]; laz[h] += laz[p]; } laz[p] = 0; } void updateSet(int idx, int x, int p=1, int l=0, int r=n+q-1) { if (l == r) { seg[0][p] = x; if (x == -inf) seg[1][p] = 0; else seg[1][p] = 1; return; } int mid = (l+r) >> 1; if (idx <= mid) updateSet(idx, x, p*2, l, mid); else updateSet(idx, x, p*2+1, mid+1, r); seg[0][p] = max(seg[0][p*2], seg[0][p*2+1]); seg[1][p] = seg[1][p*2] + seg[1][p*2+1]; } void updateSum(int idx, int x, int p=1, int l=0, int r=n+q-1) { if (idx <= l) { seg[0][p] += x; laz[p] += x; return; } int mid = (l+r) >> 1; if (idx <= mid) updateSum(idx, x, p*2, l, mid); updateSum(idx, x, p*2+1, mid+1, r); seg[0][p] = max(seg[0][p*2], seg[0][p*2+1]); seg[1][p] = seg[1][p*2] + seg[1][p*2+1]; } int queryCount(int idx, int p=1, int l=0, int r=n+q-1) { if (r <= idx) { return seg[1][p]; } pushDown(p); int mid = (l+r) >> 1; int x = queryCount(idx, p*2, l, mid); if (mid+1 <= idx) x += queryCount(idx, p*2+1, mid+1, r); return x; } vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){ n = A.size(); q = X.size(); comp.resize(n+q); for (int i = 0; i < n; i++) { a[i] = A[i]; comp[i] = make_pair(a[i], i); } for (int i = 0; i < q; i++) { x[i] = X[i]; v[i] = V[i]; comp[n+i] = make_pair(v[i], x[i]); } sort(all(comp)); comp.erase(unique(all(comp)), comp.end()); b.resize(n); for (int i = 0; i < n; i++) { a[i] = lower_bound(all(comp), make_pair(a[i], i)) - comp.begin(); b[i] = a[i]; } sort(all(b)); for (int i = 0; i < q; i++) { v[i] = lower_bound(all(comp), make_pair(v[i], x[i])) - comp.begin(); } memset(seg, 0, sizeof(seg)); memset(laz, 0, sizeof(laz)); for (int i = 0; i < n; i++) { int idx = lower_bound(all(b), a[i]) - b.begin(); updateSet(a[i], i - idx); } ans.resize(q); for (int i = 0; i < q; i++) { updateSum(a[x[i]], 1); updateSet(a[x[i]], -inf); int idx = queryCount(v[i]); updateSum(v[i], -1); updateSet(v[i], x[i] - idx); ans[i] = seg[0][1]; a[x[i]] = v[i]; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...