제출 #526642

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526642		FireGhost1301	Bubble Sort 2 (JOI18_bubblesort2)	C++11	100 / 100	1915 ms	50564 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 3;
int sz, seg[4 * N], lz[4 * N];

void init(int n) {
    sz = 1;
    while (sz < n) sz <<= 1;
}

void push(int x, int lx, int rx) {
    if (!lz[x]) return;
    seg[2 * x + 1] += lz[x], seg[2 * x + 2] += lz[x];
    lz[2 * x + 1] += lz[x], lz[2 * x + 2] += lz[x];
    lz[x] = 0;
}

void upd(int l, int r, int v, int x = 0, int lx = 0, int rx = sz) {
    if (lx >= r || rx <= l) return;
    if (lx >= l && rx <= r) {
        seg[x] += v, lz[x] += v;
        return;
    }
    push(x, lx, rx);
    int mid = (lx + rx) >> 1;
    upd(l, r, v, 2 * x + 1, lx, mid);
    upd(l, r, v, 2 * x + 2, mid, rx);
    seg[x] = max(seg[2 * x + 1], seg[2 * x + 2]);
}

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
    int n = a.size(), q = x.size(), m;

    vector<pair<int, int>> b;
    for (int i = 0; i < n; ++i) 
        b.push_back({a[i], i});
    for (int i = 0; i < q; ++i) 
        b.push_back({v[i], x[i]});
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    m = b.size();
    for (int i = 0; i < n; ++i) 
        a[i] = lower_bound(b.begin(), b.end(), make_pair(a[i], i)) - b.begin();
    for (int i = 0; i < q; ++i)
        v[i] = lower_bound(b.begin(), b.end(), make_pair(v[i], x[i])) - b.begin();

    init(m);

    for (int i = 0; i < n; ++i) {
        upd(a[i], a[i] + 1, i);
        upd(a[i] + 1, m, -1);
    }

    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        upd(a[x[i]], a[x[i]] + 1, -x[i]);
        upd(a[x[i]] + 1, m, 1);
        a[x[i]] = v[i];
        upd(a[x[i]], a[x[i]] + 1, x[i]);
        upd(a[x[i]] + 1, m, -1);
        ans[i] = seg[0];
    }

    return ans;
}

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