제출 #1210311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210311		Boomyday	Bubble Sort 2 (JOI18_bubblesort2)	C++20	0 / 100	19 ms	4048 KiB

bubblesort2

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

using namespace std;

using ll = long long;
const ll BIG = 1e9;

const ll ssz = 1<<3; // 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){
    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 -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] = A[i]*BIG + i;
    for(int i=0;i<Q;++i) quervals[i] = V[i]*BIG + 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]);
    }
    /*
    for(int i=0;i<ssz;++i){
        cout << query(i, i, 1, 0, ssz-1) << " ";
    }
    cout << endl;*/
    // output each value of the segment tree


    for(int i=0;i<Q;++i){
        // 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(numvals[X[i]], 1);
        point_update(X[i] - (quer_on(0, numvals[X[i]]) - 1), numvals[X[i]]);
        // finally, query the value
        S[i] = query(0, ssz-1, 1, 0, ssz-1);
    }
    return S;

}

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