Submission #1125731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125731		Zero_OP	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2089 ms	135304 KiB

bubblesort2

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        }
        return false;
    }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;

const int inf = 1e9;
struct segment_tree{
    vector<int> sum, st, lazy;
    segment_tree(int n) : sum(n << 2), st(n << 2, -inf), lazy(n << 2) {}

    void apply(int id, int val){
        st[id] += val;
        sum[id] += val;
        lazy[id] += val;
    }

    void down(int id){
        if(lazy[id] != 0){
            apply(id << 1, lazy[id]);
            apply(id << 1 | 1, lazy[id]);
            lazy[id] = 0;
        }
    }

    void add(int id, int l, int r, int u, int v, int val){
        if(u <= l && r <= v) apply(id, val);
        else{
            int mid = l + r >> 1;
            down(id);
            if(u <= mid) add(id << 1, l, mid, u, v, val);
            if(mid < v) add(id << 1 | 1, mid + 1, r, u, v, val);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }
    }

    void change(int id, int l, int r, int pos, int val){
        if(l == r) st[id] = val + sum[id];
        else{
            int mid = l + r >> 1;
            down(id);
            if(pos <= mid) change(id << 1, l, mid, pos, val);
            else change(id << 1 | 1, mid + 1, r, pos, val);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }
    }

    void debug(int id, int l, int r){
        if(l == r) cout << dbg(l) << dbg(st[id]) << '\n';
        else{
            int mid = l + r >> 1;
            debug(id << 1, l, mid);
            debug(id << 1 | 1, mid + 1, r);

        }
    }

    int query(){ return st[1]; }
};

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    int N = sz(A);
    int Q = sz(X);

    vector<int> val = A;
    val.insert(val.end(), all(V));

    sort(all(val));
    compact(val);

    for(auto &it : A) it = lower_bound(all(val), it) - val.begin();
    for(auto &it : V) it = lower_bound(all(val), it) - val.begin();

    int vals = sz(val);

    segment_tree tr(vals);

    vector<set<int, greater<int>>> online(vals);

    for(int i = 0; i < N; ++i){
        online[A[i]].insert(i);
    }

    for(int i = 0; i < vals; ++i){
        if(!online[i].empty()){
            tr.change(1, 0, vals - 1, i, *online[i].begin());
            tr.add(1, 0, vals - 1, i, vals - 1, -sz(online[i]));
        }
    }

    vector<int> S(Q);
    for(int i = 0; i < Q; ++i){
        tr.add(1, 0, vals - 1, A[X[i]], vals - 1, +1);
        online[A[X[i]]].erase(X[i]);

        if(online[A[X[i]]].empty()) tr.change(1, 0, vals - 1, A[X[i]], -inf);
        else tr.change(1, 0, vals - 1, A[X[i]], *online[A[X[i]]].begin());

        A[X[i]] = V[i];

        tr.add(1, 0, vals - 1, A[X[i]], vals - 1, -1);
        online[A[X[i]]].insert(X[i]);

        tr.change(1, 0, vals - 1, A[X[i]], *online[A[X[i]]].begin());
        S[i] = tr.query() + 1;
    }

    return S;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    file("task");

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for(int i = 0; i < N; ++i){
        cin >> A[i];
    }

    vector<int> X(Q), V(Q);
    for(int i = 0; i < Q; ++i){
        cin >> X[i] >> V[i];
    }

    vector<int> S = countScans(A, X, V);

    for(auto it : S) cout << it << '\n';

    return 0;
}
#endif //LOCAL

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