Submission #1210392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210392		Boomyday	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	3012 ms	156140 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll BIG = 1e9;
const ll ssz = 1<<20; // 1 << 20

const int INF = 1e9;

vector<int> seg_on(2*ssz, 0);
vector<int> seg_max(2*ssz, -INF), lz_max(2*ssz, 0);

void upd_on(int i, int x){
    i += ssz;
    seg_on[i] = x;
    i /= 2;
    while(i >= 1){

        seg_on[i] = seg_on[2*i] + seg_on[2*i+1];
        i /= 2;
    }
}
int quer_on (int l, int r){
    if (l > r) return 0;
    l += ssz;
    r += ssz;
    int res = 0;
    while(l <= r){
        if(l&1) res += seg_on[l++];
        if(!(r&1)) res += seg_on[r--];
        l /= 2;
        r /= 2;
    }
    return res;
}

void pushdown(int rt, int tl, int tr){
    seg_max[rt] += lz_max[rt];
    if (tl != tr) {
        lz_max[2*rt] += lz_max[rt];
        lz_max[2*rt+1] += lz_max[rt];
    }
    lz_max[rt] = 0;
}

int query(int l, int r, int rt, int tl, int tr){
    pushdown(rt, tl, tr);
    if (r < tl || l > tr) return -(2*INF);
    if (l <= tl && tr <= r) return seg_max[rt];
    int mid = (tl + tr) / 2;
    return max(query(l, r, 2*rt, tl, mid), query(l, r, 2*rt+1, mid+1, tr));
}

void update(int x, int l, int r, int rt, int tl, int tr){
    pushdown(rt, tl, tr);
    if (r < tl || l > tr) return;
    if (l <= tl && tr <= r) {
        lz_max[rt] += x;


        pushdown(rt, tl, tr);


        return;
    }
    int mid = (tl + tr) / 2;
    update(x, l, r, 2*rt, tl, mid);
    update(x, l, r, 2*rt+1, mid+1, tr);
    seg_max[rt] = max(seg_max[2*rt], seg_max[2*rt+1]);
}

void point_update(int x, int i){
    update(x- query(i, i, 1, 0, ssz-1), i, i, 1, 0, ssz-1);
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int Q=X.size();
	int N = A.size();
    vector<int> S(Q);

    vector<ll> numvals(N), quervals(Q);
    for(int i=0;i<N;++i) numvals[i] = BIG*A[i] + i;
    for(int i=0;i<Q;++i) quervals[i] = BIG*V[i] + X[i];
    set<ll> compress;
    for(int i=0;i<N;++i) compress.insert(numvals[i]);
    for(int i=0;i<Q;++i) compress.insert(quervals[i]);
    map<ll, int> compress_map;
    int idx = 0;
    for(auto val : compress) {
        compress_map[val] = idx++;
    }
    for(int i=0;i<N;++i) numvals[i] = compress_map[numvals[i]];
    for(int i=0;i<Q;++i) quervals[i] = compress_map[quervals[i]];
    for(int i=0;i<N;++i) upd_on(numvals[i], 1);
    // output the full segment tree of segon

    for(int i=0;i<N;++i){
        point_update( i-(quer_on(0, numvals[i]-1)), numvals[i]);
    }

    // output each value of the segment tree


    for(int i=0;i<Q;++i){
        if (numvals[X[i]] == quervals[i]){
            S[i] = query(0, ssz-1, 1, 0, ssz-1);
            continue;
        }
        // output the numvals array
        /*
        cout << "numvals: ";
        for (int j=0;j<N;++j){
            cout << numvals[j] << " ";
        }
        cout << endl;*/
        // newpos = X[i]
        // turn off the old value
        upd_on(numvals[X[i]],0);
        point_update(-INF,numvals[X[i]]);
        // update values between old and new
        // old value = numvals[X[i]]
        // new value = quervals[i]
        // if it moves from small to big, add one to the elements
        // else subtract one
        if (numvals[X[i]] < quervals[i]){
            update(1, numvals[X[i]], quervals[i], 1, 0, ssz-1);
        }
        else if (numvals[X[i]] > quervals[i]){
            update(-1, quervals[i], numvals[X[i]], 1, 0, ssz-1);
        }
        // now update numvals
        numvals[X[i]] = quervals[i];
        upd_on(quervals[i], 1);
        point_update(X[i] - (quer_on(0, quervals[i]-1) ), quervals[i]);

        S[i] = query(0, ssz-1, 1, 0, ssz-1);

    }
    return S;

}

vector<int> countScansSimple(std::vector<int> A, std::vector<int> X, std::vector<int> V){
    // count the number of passes it takes to bubblesort A
    int Q = X.size();
    int N = A.size();
    vector<int> S(Q, 0);
    vector<int> B = A; // copy of A to sort
    for (int i = 0; i < Q; ++i) {
        A[X[i]] = V[i]; // update A with the new value
        B = A; // reset B to A
        int passes = 0;
        bool sorted = false;
        while (!sorted) {
            sorted = true;
            for (int j = 0; j < N - 1; ++j) {
                if (B[j] > B[j + 1]) {
                    swap(B[j], B[j + 1]);
                    sorted = false;
                }
            }
            passes++;
        }
        S[i] = passes - 1; // subtract 1 because the last pass is not counted
    }
    return S;
}

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