Submission #1156033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156033		Hamed_Ghaffari	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1785 ms	151856 KiB

bubblesort2

#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;
#define SZ(x) int(x.size())
#define mid ((l+r)>>1)
#define all(x) x.begin(),x.end()
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
const int MXN = 1e6+5;
int seg[MXN<<2],lz[MXN<<2],N;
void U(int s,int e,int x,int l=0,int r=N,int id=1){if(s<=l&&r<=e){seg[id]+=x;lz[id]+=x;return;}if(s<mid)U(s,e,x,l,mid,id<<1);if(e>mid)U(s,e,x,mid,r,id<<1|1);seg[id]=max(seg[id<<1],seg[id<<1|1])+lz[id];}vector<int> cmp;int G(int x){return lower_bound(all(cmp),x)-cmp.begin();}set<int> pos[MXN];void E(int i,int ai){U(ai,N,1);if(i==(*pos[ai].rbegin()))U(ai,ai+1,-i+(*prev(prev(pos[ai].end()))));pos[ai].erase(i);}void I(int i, int ai) {U(ai,N,-1);if(i>(*pos[ai].rbegin()))U(ai,ai+1,-(*pos[ai].rbegin())+i);pos[ai].insert(i);}vector<int> countScans(vector<int>A,vector<int>X,vector<int>V){int n=SZ(A), q=SZ(X);rep(i,n)cmp.pb(A[i]);rep(i,q)cmp.pb(V[i]);sort(all(cmp));cmp.resize(unique(all(cmp))-cmp.begin());N=SZ(cmp);rep(i,N)pos[i].insert(-1);rep(i,n)I(i,G(A[i]));vector<int> ans(q);for(int i=0; i<q; i++) {E(X[i],G(A[X[i]]));I(X[i],G(A[X[i]]=V[i]));ans[i]=seg[1];}return ans;}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40