Submission #567797

#	Time	Username	Problem	Language	Result	Execution time	Memory
567797		balbit	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2584 ms	77896 KiB

bubblesort2

#include <bits/stdc++.h>
#ifndef BALBIT
#include "bubblesort2.h"
#endif // BALBIT
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e6+100;

ll tg[maxn*4], mx[maxn*4];

void push(int o, int l, int r){
    if (tg[o]) {
        mx[o] += tg[o];
        if (l!=r) {
            tg[o*2] += tg[o];
            tg[o*2+1] += tg[o];
        }
        tg[o] = 0;
    }
}
void MO(int L, int R, ll v, int o=1, int l=0, int r=maxn-1) {
    push(o,l,r);
    if (l>R || r<L) return;
    if (l >= L && r <= R) {
        tg[o] += v;
        push(o,l,r);
        return;
    }
    int mid = (l+r)/2;
    MO(L,R,v,o*2,l,mid);
    MO(L,R,v,o*2+1,mid+1,r);
    mx[o] = max(mx[o*2], mx[o*2+1]);
}

vector<pii> all;

void upd(int pos, bool add, int idx) {
    bug(pos, add, idx);
    MO(pos+1, maxn-1, add?-1:1);
    MO(pos, pos, (-idx-iinf) * (add?-1:1));
}

vector<signed> countScans(vector<signed> A,vector<signed> X,vector<signed> V){

    int n = SZ(A);
    MO(0, maxn-1, -iinf);

    REP(i, n) {
        all.pb({A[i], i});
    }
    int q = SZ(X);

    REP(i, q) {
        all.pb({V[i], X[i]});
    }

    SORT_UNIQUE(all);

    REP(i,n) {
        upd(lower_bound(ALL(all), pii{A[i], i}) - all.begin(), 1, i);
    }

    vector<signed> re;
    bug(mx[1]);

    REP(rnd, q) {
        int i = X[rnd];
        upd(lower_bound(ALL(all), pii{A[i], i}) - all.begin(), 0,  i);
        A[i] = V[rnd];
        upd(lower_bound(ALL(all), pii{A[i], i}) - all.begin(), 1,  i);

        re.pb(mx[1]);
        bug(mx[1]);
    }
    return re;
}


#ifdef BALBIT
signed main(){
//    countScans({1,1,1,1},{0,2},{3,1});
    countScans({1,2,3,4},{0,2},{3,1});
}
#endif // BALBIT

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