Submission #338473

#	Time	Username	Problem	Language	Result	Execution time	Memory
338473		KoD	Bubble Sort 2 (JOI18_bubblesort2)	C++17	38 / 100	9080 ms	55276 KiB

bubblesort2

#include <bits/stdc++.h>
 
template <class T>
using Vec = std::vector<T>;

struct Fenwick {
    Vec<int> data;
    Fenwick(int n): data(n + 1) { }

    void add(int i, int x) {
        i += 1;
        while (i < (int) data.size()) {
            data[i] += x;
            i += (i & -i);
        }
    }

    int get(int i) {
        int ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= (i & -i);
        }
        return ret;
    }
};


struct Mn {
    int value;
    static Mn id() {
        return Mn { -1000000000 };
    }
    Mn operator + (const Mn other) const {
        return Mn { std::max(value, other.value) };
    }
};
 
struct Ef {
    int add;
    static Ef id() {
        return Ef { 0 };
    }
    Ef operator + (const Ef other) const {
        return Ef { add + other.add };
    }
};

Mn operator + (const Mn mn, const Ef ef) {
    return Mn { mn.value + ef.add };
}
 
struct Segtree {
    struct Node {
        Mn mn;
        Ef ef;
    };
 
    void fetch(const int i) {
        data[i].mn = data[i * 2 + 0].mn + data[i * 2 + 1].mn;
    }
    void apply(const int i, const Ef ef) {
        data[i].mn = data[i].mn + ef;
        data[i].ef = data[i].ef + ef;
    }
    void flush(const int i) {
        apply(i * 2 + 0, data[i].ef);
        apply(i * 2 + 1, data[i].ef);
    }
 
    static int ctzr(const int i) {
        return __builtin_ctzll(i);
    }
    static int height(const int i) {
        return 64 - __builtin_clzll(i);
    }
 
    void pushdown(const int i) {
        const auto lsb = ctzr(i);
        for (int d = height(i); --d > lsb;) {
            flush(i >> d);
        }
    }
    void pullup(int i) {
        i >>= ctzr(i);
        while (i != 1) {
            i >>= 1;
            fetch(i);
        }
    }
 
    Vec<Node> data;
    Segtree(const Vec<int> &vec) {
        const auto size = vec.size();
        data.resize(size * 2, Node { Mn::id(), Ef::id() });
        for (int i = 0; i < size; ++i) {
            data[size + i].mn.value = vec[i];
        }
        for (int i = size - 1; i > 0; --i) {
            fetch(i);
        }
    }
 
    void operate(int l, int r, const int x) {
        l += size();
        r += size();
        pushdown(l);
        pushdown(r);
        const auto cl = l;
        const auto cr = r;
        const auto ef = Ef { x };
        while (l < r) {
            if (l & 1) {
                apply(l, ef);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                apply(r, ef);
            }
            l >>= 1;
            r >>= 1;
        }
        pullup(cl);
        pullup(cr);
    }
 
    int fold(int l, int r) {
        l += size();
        r += size();
        pushdown(l);
        pushdown(r);
        Mn mn = Mn::id();
        while (l < r) {
            if (l & 1) {
                mn = mn + data[l].mn;
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                mn = mn + data[r].mn;
            }
            l >>= 1;
            r >>= 1;
        }
        return mn.value;
    } 

    int assign(int i, int x) {
        i += size();
        pushdown(i);
        pushdown(i + 1);
        data[i].mn = Mn { x };
        data[i].ef = Ef::id();
        while (i > 1) {
            i >>= 1;
            fetch(i);
        }
    }
 
    int size() const {
        return data.size() / 2;
    }
};
 
Vec<int> countScans(Vec<int> A, Vec<int> X, Vec<int> V) {
    const int N = A.size();
    const int Q = X.size();
    if (N <= 8000 && Q <= 8000) {
        Vec<int> big(N);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < i; ++j) {
                if (A[j] > A[i]) {
                    big[i] += 1;
                }
            }
        }
        Vec<int> ret(Q);
        for (int i = 0; i < Q; ++i) {
            for (int j = X[i] + 1; j < N; ++j) {
                if (A[X[i]] <= A[j] && V[i] > A[j]) {
                    big[j] += 1;
                }
                if (A[X[i]] > A[j] && V[i] <= A[j]) {
                    big[j] -= 1;
                }
            }
            A[X[i]] = V[i];
            big[X[i]] = 0;
            for (int j = 0; j < X[i]; ++j) {
                if (A[j] > A[X[i]]) {
                    big[X[i]] += 1;
                }
            }
            ret[i] = *std::max_element(big.begin(), big.end());
        }
        return ret;
    }
    else {
        for (auto &x: A) {
            x -= 1;
            if (x >= 100) {
                return { };
            }
        }
        for (auto &x: V) {
            x -= 1;
            if (x >= 100) {
                return { };
            }
        }
        Vec<Fenwick> fen(100, Fenwick(N));
        Vec<Segtree> seg(100, Segtree(Vec<int>(N, -1000000000)));
        for (int i = 0; i < N; ++i) {
            fen[A[i]].add(i, 1);
            int sum = 0;
            for (int j = V[i] + 1; j < 100; ++j) {
                sum += fen[j].get(i);
            }
            seg[A[i]].assign(i, sum);
        }
        Vec<int> ret(Q);
        for (int i = 0; i < Q; ++i) {
            int sum = 0;
            for (int j = V[i] + 1; j < 100; ++j) {
                sum += fen[j].get(X[i]);
            }
            fen[A[X[i]]].add(X[i], -1);
            seg[A[X[i]]].assign(X[i], -1000000000);
            fen[V[i]].add(X[i], 1);
            seg[V[i]].assign(X[i], sum);
            if (A[X[i]] < X[i]) {
                for (int j = A[X[i]]; j < V[j]; ++j) {
                    seg[j].operate(X[i] + 1, N, 1);
                }
            }
            else {
                for (int j = V[i]; j < A[X[i]]; ++j) {
                    seg[j].operate(X[i] + 1, N, -1);
                }
            }
            A[X[i]] = V[i];
            for (int j = 0; j < 100; ++j) {
                ret[i] = std::max(ret[i], seg[j].fold(0, N));
            }
        }
        return ret;
    }
}
 
#ifdef __APPLE__
int main() {
    int N, Q;
    std::cin >> N >> Q;
    Vec<int> A(N);
    Vec<int> X(Q), V(Q);
    for (auto &x: A) {
        std::cin >> x;
    }
    for (int i = 0; i < Q; ++i) {
        std::cin >> X[i] >> V[i];
    }
    for (auto x: countScans(A, X, V)) {
        std::cout << x << '\n';
    }
    return 0;
}
#endif

Compilation message (stderr)

bubblesort2.cpp: In constructor 'Segtree::Segtree(Vec<int>&)':
bubblesort2.cpp:96:27: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   96 |         for (int i = 0; i < size; ++i) {
      |                         ~~^~~~~~
bubblesort2.cpp: In member function 'int Segtree::assign(int, int)':
bubblesort2.cpp:159:5: warning: no return statement in function returning non-void [-Wreturn-type]
  159 |     }
      |     ^

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