Submission #1212161

#TimeUsernameProblemLanguageResultExecution timeMemory
1212161adhityamvBubble Sort 2 (JOI18_bubblesort2)C++20
100 / 100
2555 ms172608 KiB
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <climits> #include <cmath> #include <complex> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <vector> #include <stack> using namespace std; #define ll long long #define mp make_pair #define fi first #define pii pair<int,int> #define se second //const int INF=1000000000000000000; const int INF=1e9; const int N=1000000; const int M=998244353; const int ln=20; template<typename T> std::ostream& operator<< (std::ostream& os,pair<T,T> p){ return os << p.fi << "," << p.se << " "; } int get(vector<int> a){ // I need to know how many atleast than an element x // for this, store in a sorted array //for(int i:a) cout << i << " "; //cout << "\n"; vector<int> ts=a; sort(ts.begin(),ts.end()); int ans=0; int n=a.size(); int mn=INF; for(int i=n-1;i>=0;i--){ if(a[i]>=mn) continue; // we need how many atleast mn int cnt=n-(lower_bound(ts.begin(),ts.end(),a[i]+1)-ts.begin()); ans=max(ans,cnt-(n-1-i)); mn=a[i]; } return ans; } struct lazysegtree{ int n; vector<int> seg; vector<int> lazy; lazysegtree(int nn){ n=nn; for(int i=0;i<4*n;i++){ seg.push_back(0); lazy.push_back(0); } } void UpdateLazy(int l,int r,int pos){ if(lazy[pos]==0) return; seg[pos]+=lazy[pos]; if(l!=r){ lazy[2*pos]+=lazy[pos]; lazy[2*pos+1]+=lazy[pos]; } lazy[pos]=0; } void Update(int l,int r,int pos,int ql,int qr,int val){ UpdateLazy(l,r,pos); if(ql>r || qr<l){ return; } if(ql<=l && qr>=r){ lazy[pos]+=val; UpdateLazy(l,r,pos); return; } int m=(l+r)/2; Update(l,m,2*pos,ql,qr,val); Update(m+1,r,2*pos+1,ql,qr,val); seg[pos]=max(seg[2*pos],seg[2*pos+1]); } int mx(){ return seg[1]; } }; vector<int> countScans(vector<int> oa,vector<int> x,vector<int> ov){ vector<int> ans; int q=x.size(); vector<int> ts; int n=oa.size(); for(int i=0;i<n;i++) ts.push_back(oa[i]); for(int i=0;i<q;i++) ts.push_back(ov[i]); sort(ts.begin(),ts.end()); ts.erase(unique(ts.begin(),ts.end()),ts.end()); int mxn=ts.size(); int a[n]; int v[q]; for(int i=0;i<n;i++) a[i]=(lower_bound(ts.begin(),ts.end(),oa[i])-ts.begin()); for(int i=0;i<q;i++) v[i]=(lower_bound(ts.begin(),ts.end(),ov[i])-ts.begin()); reverse(a,a+n); for(int i=0;i<q;i++) x[i]=n-1-x[i]; // in segtree, we will store how many >i-first index of i set<int> allind[mxn]; for(int i=0;i<n;i++) allind[a[i]].insert(i); for(int i=0;i<mxn;i++) allind[i].insert(n); // operations are range add , element update, and full max lazysegtree seg(mxn); for(int i=0;i<n;i++){ if(a[i]>0) seg.Update(0,mxn-1,1,0,a[i]-1,1); } for(int i=0;i<mxn;i++){ int find=*allind[i].begin(); seg.Update(0,mxn-1,1,i,i,-find); } int find; for(int i=0;i<q;i++){ if(a[x[i]]>0) seg.Update(0,mxn-1,1,0,a[x[i]]-1,-1); find=*allind[a[x[i]]].begin(); seg.Update(0,mxn-1,1,a[x[i]],a[x[i]],find); allind[a[x[i]]].erase(x[i]); find=*allind[a[x[i]]].begin(); seg.Update(0,mxn-1,1,a[x[i]],a[x[i]],-find); a[x[i]]=v[i]; if(a[x[i]]>0) seg.Update(0,mxn-1,1,0,a[x[i]]-1,1); find=*allind[a[x[i]]].begin(); seg.Update(0,mxn-1,1,a[x[i]],a[x[i]],find); allind[a[x[i]]].insert(x[i]); find=*allind[a[x[i]]].begin(); seg.Update(0,mxn-1,1,a[x[i]],a[x[i]],-find); ans.push_back(seg.mx()); } 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...