Submission #1270569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270569		uranium235	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2732 ms	102472 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ost = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using tupl = tuple<int, int, int, int>;
using pii = pair<int, int>;
const int inf = INT32_MIN / 2;

struct state {
    int max, lazyAdd;
    void merge(state &l, state &r)  {
        max = std::max(l.max, r.max);
    }
    void push(state &l, state &r) {
        l.apply(lazyAdd);
        r.apply(lazyAdd);
        lazyAdd = 0;
    }
    void apply(int x) {
        max += x;
        lazyAdd += x;
    }
};


struct segtree {
    public:
        int n, lim;
        vector<state> a;
        vector<int> mapping;
        segtree(int n, int lim, vector<tupl> &x) : n(n), lim(lim), a(4 * n), mapping(n) {
            build(0, n - 1, 1, x);
        }
        void build(int l, int r, int v, vector<tupl> &x) {
            if (l == r)  {
                if (get<2>(x[l]) < lim) {
                    a[v].apply(get<1>(x[l]) - get<3>(x[l]));
                } else {
                    a[v].apply(inf);
                }
                mapping[l] = v;
            } else {
                int m = (l + r) / 2;
                build(l, m, 2 * v, x);
                build(m + 1, r, 2 * v + 1, x);
                a[v].merge(a[2 * v], a[2 * v + 1]);
            }
        }
        void upd(int ql, int qr, int l, int r, int v, int x, bool y) {
            if (qr < l || r < ql) return;
            else if (ql <= l && r <= qr) {
                if (!y) a[v].apply(x);
                else {
                    a[v].max = a[v].lazyAdd = x;
                }
            }
            else {
                a[v].push(a[2 * v], a[2 * v + 1]);
                int m = (l + r) / 2;
                upd(ql, qr, l, m, 2 * v, x, y);
                upd(ql, qr, m + 1, r, 2 * v + 1, x, y);
                a[v].merge(a[2 * v], a[2 * v + 1]);
            }
        }
        void upd(int ql, int qr, int x, bool y) {
            assert(0 <= ql && ql <= qr && qr < n);
            return upd(ql, qr, 0, n - 1, 1, x, y);
        }
        state& at(int i) {
            return a[mapping[i]];
        }
        void print() {
            for (int i = 0; i < n; i++) {
                cout << a[mapping[i]].lazyAdd << " ";
            }
            cout << endl;
        }
};

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
    int q = x.size(), n = a.size();
    vector<tupl> entries;
    entries.reserve(n + q);
    ost<pii> oset;
    for (int i = 0; i < n; i++) oset.insert({a[i], i});
    for (int i = 0; i < n; i++) entries.push_back({a[i], i, i, oset.order_of_key({a[i], i})});
    for (int i = 0; i < q; i++) {
        bool removed = oset.erase({a[x[i]], x[i]});
        assert(removed);
        oset.insert({v[i], x[i]});
        entries.push_back({v[i], x[i], i + n, oset.order_of_key({v[i], x[i]})});
        a[x[i]] = v[i];
    }
    sort(entries.begin(), entries.end());

    vector<int> where(n + q);
    for (int i = 0; i < n + q; i++) where[get<2>(entries[i])] = i;
    vector<int> cur(n);
    copy(where.begin(), where.begin() + n, cur.begin());

    segtree tree(n + q, n, entries);    
    vector<int> answer(q);
    for (int i = 0; i < q; i++) {
        int prev = cur[x[i]];
        int now = where[i + n];
        tupl& ptr = entries[now];
        tree.upd(prev, prev, inf, true);
        tree.upd(now, now, get<1>(ptr) - get<3>(ptr), true);
        if (prev < now - 1) {
            tree.upd(prev + 1, now - 1, 1, false);
        } else if (prev > now + 1) {
            tree.upd(now + 1, prev - 1, -1, false);
        }
        
        // tree.print();
        // for (tupl& i : entries) cout << "{" << get<0>(i) << ", " << get<1>(i) << ", " << get<3>(i) << "} ";
        // cout << endl;
        cur[x[i]] = now;
        answer[i] = tree.a[1].max;
    }

    return answer;
}

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