Submission #145589

#TimeUsernameProblemLanguageResultExecution timeMemory
145589bharat2002Bubble Sort 2 (JOI18_bubblesort2)C++14
100 / 100
4807 ms161224 KiB
/*input 8 1 1 1 1 1 1 2 1 */ #include<bits/stdc++.h> using namespace std; const int N=1e6 + 1099; const int mod=1e9 + 7; #define pii pair<int, int> #define f first #define s second #define mp make_pair int n;map<int, int> conv; multiset<int> positions[N]; class tree { int tree[4*N], lazy[4*N], ql, qr, val; void prop(int i, int l, int r) { tree[i]+=lazy[i]; if(l!=r) { lazy[2*i]+=lazy[i];lazy[2*i+1]+=lazy[i]; } lazy[i]=0; } void update(int i=1, int l=1, int r=N-1) { prop(i, l, r); if(l>qr||r<ql) return; if(l>=ql&&r<=qr) { lazy[i]+=val;prop(i, l, r); return; } int mid=(l+r)>>1;update(2*i, l, mid);update(2*i+1, mid+1, r);tree[i]=max(tree[2*i], tree[2*i+1]); } public: void remove(int ind, int el) { int prevmax=(*positions[el].rbegin()); positions[el].erase(ind); if(!positions[el].empty()) prevmax=(*positions[el].rbegin()) - prevmax; else prevmax*=-1; ql=qr=el;val=prevmax; if(val!=0) update(); ql=el+1;qr=N-1;val=+1; if(!positions[el].empty()) ql--; update(); } void add(int ind, int el) { int prevmax=0; if(!positions[el].empty()) prevmax=(*positions[el].rbegin()); positions[el].insert(ind); prevmax=(*positions[el].rbegin() - prevmax); ql=qr=el;val=prevmax; if(val!=0) update(); ql=el+1;qr=N-1;val=-1; if(positions[el].size()>1) ql--; update(); } int qry() { return tree[1]; } }; tree Segtree; vector<int> countScans(vector<int> arr, vector<int> pos, vector<int> nval) { n=arr.size();int q=pos.size();vector<int> ans; conv.clear(); for(auto i:arr) conv[i]=0; for(auto i:nval) conv[i]=0; int curv=1; for(auto &i:conv) i.s=curv++; for(int i=0;i<n;i++) {arr[i]=conv[arr[i]];Segtree.add(i, arr[i]);} for(auto &i:nval) i=conv[i]; //cout<<Segtree.qry()<<endl; for(int i=0;i<q;i++) { Segtree.remove(pos[i], arr[pos[i]]); Segtree.add(pos[i], nval[i]);arr[pos[i]]=nval[i]; ans.push_back(Segtree.qry()); } 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...