Submission #919717

#TimeUsernameProblemLanguageResultExecution timeMemory
919717KiaRezBubble Sort 2 (JOI18_bubblesort2)C++17
0 / 100
27 ms29784 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define endl '\n' const int N = 1e6+2e5+23, lg = 20; ll Mod = 1e9+7; //998244353; inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;} inline ll poww(ll a, ll b, ll mod=Mod) { ll ans = 1; a=MOD(a, mod); while (b) { if (b & 1) ans = MOD(ans*a, mod); b >>= 1; a = MOD(a*a, mod); } return ans; } int n, q, a[N], seg[3*N], lazy[3*N]; set<int> st; vector<int> comp; int get(int x) { int ptr = lower_bound(all(comp), x) - comp.begin() + 1; return ptr; } inline void pushdown(int ind) { seg[ind] += lazy[ind]; (ind<(1<<lg)) && (lazy[2*ind] += lazy[ind]); (ind<(1<<lg)) && (lazy[2*ind+1] += lazy[ind]); lazy[ind] = 0; } void update(int l, int r, int y, int ind=1, int lc=1, int rc=(1<<lg)+1) { pushdown(ind); if(l>=rc || lc>=r) return; if(lc>=l && rc<=r) { lazy[ind] += y; pushdown(ind); return; } int mid = (lc+rc)/2; update(l, r, y, 2*ind, lc, mid); update(l, r, y, 2*ind+1, mid, rc); seg[ind] = max(seg[2*ind], seg[2*ind+1]); } void update2(int pos, int y, int ind=1, int lc=1, int rc=(1<<lg)+1) { pushdown(ind); if(ind>=(1<<lg)) { seg[ind] = y; return; } int mid = (lc+rc)/2; if(pos<mid) update2(pos, y, 2*ind, lc, mid); else update2(pos, y, 2*ind+1, mid, rc); seg[ind] = max(seg[2*ind], seg[2*ind+1]); } int seg2[3*N]; void upd(int ind, int val) { if(ind==0) return; if(ind>=(1<<lg)) seg2[ind]=val; else seg2[ind] = max(seg2[2*ind], seg2[2*ind+1]); upd(ind/2, val); } int fnd(int val, int ind=1, int lc=1, int rc=(1<<lg)+1) { if(ind >= (1<<lg)) return lc; int mid = (lc+rc)/2; if(seg2[2*ind] >= val) return fnd(val, 2*ind, lc, mid); return fnd(val, 2*ind+1, mid, rc); } int fen[N]; void ufen(int x, int val) { while(x < N) { fen[x] += val; x += (x&(-x)); } } int qfen(int pos) { int res = 0; while(pos > 0) { res += fen[pos]; pos -= (pos&(-pos)); } return res; } /* int main () { cin>>n>>q; vector<int> A(n), V(q), X(q); for(int i=1; i<=n; i++) cin>>A[i-1]; for(int i=1; i<=q; i++) cin>>X[i-1]>>V[i-1]; for(int i=1; i<=q; i++) comp.pb(V[i-1]), X[i-1]++; sort(all(comp)); comp.resize(unique(all(comp)) - comp.begin()); for(int i=1; i<=n; i++) a[i] = get(A[i-1]); for(int i=1; i<=q; i++) V[i-1] = get(V[i-1]); int mn = 1e9+1; for(int i=n; i>=1; i--) { if(a[i] < mn) { st.insert(i); mn = a[i]; upd(i+(1<<lg)-1, a[i]); } else { update2(i+(1<<lg)-1, -n-1); } if (a[i] > mn) { int pos = fnd(a[i]); update(i, pos+1, 1); } ufen(a[i], 1); } vector<int> ans; for(int pos,x,v,i=1; i<=q; i++) { x=X[i-1], v=V[i-1]; ufen(a[x], -1); ufen(v, 1); if(st.find(x) != st.end()) { update2(x+(1<<lg)-1, -n); st.erase(x); } else { pos = max(fnd(a[x]), x); update(x, pos, -1); } a[x] = v; st.insert(x); upd(x+(1<<lg)-1, a[x]); vector<int> vec; while(size(st) > 0) { auto it = st.lower_bound(x); if(it==st.begin()) break; it--; if(a[(*it)] >= a[x]) { update2((*it), -n); upd((*it)+(1<<lg)-1, 0); st.erase((*it)); } else break; } auto it = st.lower_bound(x); it++; if(it==st.end() || a[(*it)] > a[x]) { update2(x, qfen(N-1) - qfen(a[x]) - (n-x)); } else { upd(x+(1<<lg)-1, 0); st.erase(x); int pos = max(x, fnd(a[x])); update(x, pos, 1); } cout<<seg[1]<<endl; } return 0; } */ vector<int> countScans (vector<int> A, vector<int> X, vector<int> V) { n=size(A), q=size(X); for(int i=1; i<=n; i++) comp.pb(A[i-1]); for(int i=1; i<=q; i++) comp.pb(V[i-1]), X[i-1]++; sort(all(comp)); comp.resize(unique(all(comp)) - comp.begin()); for(int i=1; i<=n; i++) a[i] = get(A[i-1]); for(int i=1; i<=q; i++) V[i-1] = get(V[i-1]); vector<int> ans; int mn = 1e9+1; for(int i=n; i>=1; i--) { if(a[i] < mn) { st.insert(i); mn = a[i]; upd(i+(1<<lg)-1, a[i]); } else { update2(i+(1<<lg)-1, -n-1); } if (a[i] > mn) { int pos = fnd(a[i]); update(i, pos+1, 1); } ufen(a[i], 1); } for(int pos,x,v,i=1; i<=q; i++) { x=X[i-1], v=V[i-1]; ufen(a[x], -1); ufen(v, 1); if(st.find(x) != st.end()) { update2(x+(1<<lg)-1, -n); st.erase(x); } else { pos = max(fnd(a[x]), x); update(x, pos, -1); } a[x] = v; st.insert(x); upd(x+(1<<lg)-1, a[x]); vector<int> vec; while(size(st) > 0) { auto it = st.lower_bound(x); if(it==st.begin()) break; it--; if(a[(*it)] >= a[x]) { update2((*it), -n); upd((*it)+(1<<lg)-1, 0); st.erase((*it)); } else break; } auto it = st.lower_bound(x); it++; if(it==st.end() || a[(*it)] > a[x]) { update2(x, qfen(N-1) - qfen(a[x]) - (n-x)); } else { upd(x+(1<<lg)-1, 0); st.erase(x); int pos = max(x, fnd(a[x])); update(x, pos, 1); } ans.pb(seg[1]); } 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...