Submission #964104

#	Time	Username	Problem	Language	Result	Execution time	Memory
964104		Trisanu_Das	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1808 ms	54732 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using vi=vector<int>;
#define mp make_pair
#define lb lower_bound
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int N=2e6+5;
vi a;
int seg[N], lzy[N];
vector<pair<int,int>> v;
 
void upd(int i, int j, int vv, int p=0, int l=1, int r=sz(v)){
    if(i>r or j<l) return;
    if(i<=l and r<=j){ seg[p]+=vv,lzy[p]+=vv; return; }
    int mid = (l+r)/2; int rp = p+2*(mid-l+1);
    if(i<=mid) upd(i,j,vv,p+1,l,mid);
    if(j>mid) upd(i,j,vv,rp,mid+1,r);
    seg[p] = max(seg[p+1],seg[rp])+lzy[p];
}
 
void add(int i, int x){
    int j = lb(all(v),mp(a[i],i))-begin(v);
    int j2 = lb(all(v),mp(a[i],-1))-begin(v);
    upd(j,j,i*x), upd(j2,sz(v),-x);
}
 
vi countScans(vi A, vi x, vi y){
    int n = sz(A), q = sz(x); vi ans; a.resize(n+1);
    for(int i = 1; i <= n; i++) a[i] = A[i - 1], v.pb({a[i],i});
    for(int i = 0; i < q; i++) v.pb({y[i], ++x[i]});
    sort(all(v)); v.erase(unique(all(v)),end(v));
    for(int i = 1; i <= n; i++) add(i,1);
    for(int i = 0; i < q; i++) 
      add(x[i], -1), a[x[i]] = y[i], add(x[i], 1),ans.pb(seg[0]);
    return ans;
}

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