Submission #546050

#	Time	Username	Problem	Language	Result	Execution time	Memory
546050		alextodoran	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	91 ms	7128 KiB

bubblesort2

#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 500000;
const int Q_MAX = 500000;
const int V_MAX = 1000000;

const int INF = INT_MAX / 2;

int N, Q;
int arr[N_MAX];

struct Query {
    int pos;
    int val;
};
Query queries[Q_MAX];

int V;

void compress () {
    vector <pair <int, int>> aux;
    for (int i = 0; i < N; i++) {
        aux.push_back(make_pair(arr[i], i));
    }
    for (int i = 0; i < Q; i++) {
        aux.push_back(make_pair(queries[i].val, queries[i].pos));
    }
    sort(aux.begin(), aux.end());
    aux.resize(unique(aux.begin(), aux.end()) - aux.begin());
    map <pair <int, int>, int> mp;
    for (pair <int, int> p : aux) {
        mp[p] = V++;
    }
    for (int i = 0; i < N; i++) {
        arr[i] = mp[make_pair(arr[i], i)];
    }
    for (int i = 0; i < Q; i++) {
        queries[i].val = mp[make_pair(queries[i].val, queries[i].pos)];
    }
}

struct Info {
    int cnt;
    int maxVal;
    int lazy;
    void setVal (const int &y) {
        maxVal = y;
        cnt = (y != -INF);
    }
};
Info operator + (const Info &x, const Info &y) {
    return Info{x.cnt + y.cnt, max(x.maxVal, y.maxVal), 0};
}
void operator += (Info &x, const int &y) {
    x.maxVal += y;
    x.lazy += y;
}

Info SGT[V_MAX * 4 + 2];

void build (int node, int l, int r) {
    if (l == r) {
        SGT[node].setVal(-INF);
    } else {
        int mid = (l + r) / 2;
        int lSon = node * 2, rSon = node * 2 + 1;
        build(lSon, l, mid);
        build(rSon, mid + 1, r);
        SGT[node] = SGT[lSon] + SGT[rSon];
    }
}
void build () {
    build(1, 0, V - 1);
}

void updateAdd (int node, int l, int r, int ul, int ur, int uadd) {
    if (ul <= l && r <= ur) {
        SGT[node] += uadd;
    } else {
        int mid = (l + r) / 2;
        int lSon = node * 2, rSon = node * 2 + 1;
        SGT[lSon] += SGT[node].lazy;
        SGT[rSon] += SGT[node].lazy;
        if (ul <= mid) {
            updateAdd(lSon, l, mid, ul, ur, uadd);
        }
        if (mid + 1 <= ur) {
            updateAdd(rSon, mid + 1, r, ul, ur, uadd);
        }
        SGT[node] = SGT[lSon] + SGT[rSon];
    }
}
void updateAdd (int ul, int ur, int uadd) {
    updateAdd(1, 0, V - 1, ul, ur, uadd);
}

void updateSet (int node, int l, int r, int upos, int uset) {
    if (l == r) {
        SGT[node].setVal(uset);
    } else {
        int mid = (l + r) / 2;
        int lSon = node * 2, rSon = node * 2 + 1;
        SGT[lSon] += SGT[node].lazy;
        SGT[rSon] += SGT[node].lazy;
        if (upos <= mid) {
            updateSet(lSon, l, mid, upos, uset);
        } else {
            updateSet(rSon, mid + 1, r, upos, uset);
        }
        SGT[node] = SGT[lSon] + SGT[rSon];
    }
}
void updateSet (int upos, int uset) {
    updateSet(1, 0, V - 1, upos, uset);
}

int queryCnt (int node, int l, int r, int qr) {
    if (r <= qr) {
        return SGT[node].cnt;
    } else {
        int mid = (l + r) / 2;
        int lSon = node * 2, rSon = node * 2 + 1;
        SGT[lSon] += SGT[node].lazy;
        SGT[rSon] += SGT[node].lazy;
        SGT[node].lazy = 0;
        int cnt = queryCnt(lSon, l, mid, qr);
        if (mid + 1 <= qr) {
            cnt += queryCnt(rSon, mid + 1, r, qr);
        }
        return cnt;
    }
}
int queryCnt (int qr) {
    return queryCnt(1, 0, V - 1, qr);
}

vector <int> countScans (vector <int> _A, vector <int> _X, vector <int> _V) {
    N = (int) _A.size(); Q = _X.size();
    for (int i = 0; i < N; i++) {
        arr[i] = _A[i];
    }
    for (int i = 0; i < Q; i++) {
        queries[i] = Query{_X[i], _V[i]};
    }
    compress();

    build();
    for (int i = 0; i < N; i++) {
        int smaller = queryCnt(arr[i]);
        updateAdd(arr[i], V - 1, -1);
        updateSet(arr[i], i - smaller);
    }
    vector <int> answer(Q);
    for (int i = 0; i < Q; i++) {
        updateSet(queries[i].pos, -INF);
        if (queries[i].val <= arr[queries[i].pos]) {
            updateAdd(queries[i].val, arr[queries[i].pos], -1);
        } else {
            updateAdd(arr[queries[i].pos], queries[i].val, +1);
        }
        int smaller = queryCnt(queries[i].val);
        updateSet(queries[i].val, queries[i].pos - smaller);
        arr[queries[i].pos] = queries[i].val;
        answer[i] = SGT[1].maxVal;
    }
    return answer;
}

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