Submission #58374

#	Time	Username	Problem	Language	Result	Execution time	Memory
58374		Benq	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	6710 ms	111696 KiB

bubblesort2

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

template<class T, int SZ> struct LazySegTree {
    T sum[2*SZ], mx[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
    
    LazySegTree() {
        F0R(i,2*SZ) mx[i] = -MOD, sum[i] = 0;
        memset (lazy,0,sizeof lazy);
    }
    
    void push(int ind, int L, int R) {
        mx[ind] += lazy[ind];
        if (L != R) lazy[2*ind] += lazy[ind], lazy[2*ind+1] += lazy[ind];
        lazy[ind] = 0;
    }
    
    void pull(int ind) {
        sum[ind] = sum[2*ind]+sum[2*ind+1];
        mx[ind] = max(mx[2*ind],mx[2*ind+1]);
    }
    
    void build() {
        F0Rd(i,SZ) pull(i);
    }
    
    T qsum(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (lo > R || L > hi) return 0;
        if (lo <= L && R <= hi) return sum[ind];
        
        int M = (L+R)/2;
        return qsum(lo,hi,2*ind,L,M) + qsum(lo,hi,2*ind+1,M+1,R);
    }

    T qmax(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (lo > R || L > hi) return -MOD;
        if (lo <= L && R <= hi) return mx[ind];
        
        int M = (L+R)/2;
        return max(qmax(lo,hi,2*ind,L,M), qmax(lo,hi,2*ind+1,M+1,R));
    }
    
    void se(int pos, pi val, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (R < pos || pos < L) return;
        if (L == R) {
            mx[ind] = val.f, sum[ind] = val.s;
            return;
        }
        int M = (L+R)/2;
        se(pos,val,2*ind,L,M), se(pos,val,2*ind+1,M+1,R);
        pull(ind);
    }
    
    void upd(int lo, int hi, int inc, int ind = 1, int L = 0, int R = SZ-1) {
        push(ind,L,R);
        if (hi < L || R < lo) return;
        if (lo <= L && R <= hi) {
            lazy[ind] = inc;
            push(ind,L,R);
            return;
        }
        
        int M = (L+R)/2;
        upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
        pull(ind);
    }
};

LazySegTree<int,1<<20> L;

#include "bubblesort2.h"
map<pi,int> m;
vpi v; 
vi cur;

void init(vi A, vi X, vi V) {
    F0R(i,sz(A)) {
        m[{A[i],i}] = 0;
        v.pb({A[i],i});
    }
    F0R(i,sz(V)) m[{V[i],X[i]}] = 0;
    int co = 0;
    for (auto& a: m) a.s = co++;
    sort(all(v));
    
    cur = A;
    F0R(i,sz(v)) {
        int ind = m[v[i]];
        L.mx[ind^(1<<20)] = v[i].s-i;
        L.sum[ind^(1<<20)] = 1;
    }
    
    L.build();
}

// // store current pos - correct pos based on {value, correct pos}

int process(int x, int v) {
    int pos = m[{cur[x],x}];
    L.upd(pos+1,(1<<20)-1,1);
    L.se(pos,{-MOD,0});
    
    cur[x] = v;
    
    pos = m[{cur[x],x}];
    L.upd(pos+1,(1<<20)-1,-1);
    L.se(pos,{x-L.qsum(0,pos-1),1});
    
    return L.qmax(0,(1<<20)-1);
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
    init(A,X,V);
    vi answer; F0R(i,sz(V)) answer.pb(process(X[i],V[i]));
	return answer;
}

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