oj.uz

Submission #338473

# Submission time Handle Problem Language Result Execution time Memory
338473 2020-12-23T08:55:58 Z KoD Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 9000 ms 55276 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 31 ms 492 KB Output is correct
4 Correct 31 ms 620 KB Output is correct
5 Correct 25 ms 512 KB Output is correct
6 Correct 17 ms 492 KB Output is correct
7 Correct 20 ms 364 KB Output is correct
8 Correct 23 ms 492 KB Output is correct
9 Correct 25 ms 492 KB Output is correct
10 Correct 21 ms 492 KB Output is correct
11 Correct 21 ms 512 KB Output is correct
12 Correct 21 ms 492 KB Output is correct
13 Correct 20 ms 492 KB Output is correct
14 Correct 20 ms 492 KB Output is correct
15 Correct 20 ms 492 KB Output is correct
16 Correct 18 ms 492 KB Output is correct
17 Correct 19 ms 492 KB Output is correct
18 Correct 19 ms 492 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 31 ms 492 KB Output is correct
4 Correct 31 ms 620 KB Output is correct
5 Correct 25 ms 512 KB Output is correct
6 Correct 17 ms 492 KB Output is correct
7 Correct 20 ms 364 KB Output is correct
8 Correct 23 ms 492 KB Output is correct
9 Correct 25 ms 492 KB Output is correct
10 Correct 21 ms 492 KB Output is correct
11 Correct 21 ms 512 KB Output is correct
12 Correct 21 ms 492 KB Output is correct
13 Correct 20 ms 492 KB Output is correct
14 Correct 20 ms 492 KB Output is correct
15 Correct 20 ms 492 KB Output is correct
16 Correct 18 ms 492 KB Output is correct
17 Correct 19 ms 492 KB Output is correct
18 Correct 19 ms 492 KB Output is correct
19 Correct 380 ms 760 KB Output is correct
20 Correct 495 ms 876 KB Output is correct
21 Correct 314 ms 812 KB Output is correct
22 Correct 391 ms 748 KB Output is correct
23 Correct 330 ms 748 KB Output is correct
24 Correct 315 ms 748 KB Output is correct
25 Correct 306 ms 748 KB Output is correct
26 Correct 364 ms 748 KB Output is correct
27 Correct 292 ms 748 KB Output is correct
28 Correct 285 ms 876 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9080 ms 55276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 31 ms 492 KB Output is correct
4 Correct 31 ms 620 KB Output is correct
5 Correct 25 ms 512 KB Output is correct
6 Correct 17 ms 492 KB Output is correct
7 Correct 20 ms 364 KB Output is correct
8 Correct 23 ms 492 KB Output is correct
9 Correct 25 ms 492 KB Output is correct
10 Correct 21 ms 492 KB Output is correct
11 Correct 21 ms 512 KB Output is correct
12 Correct 21 ms 492 KB Output is correct
13 Correct 20 ms 492 KB Output is correct
14 Correct 20 ms 492 KB Output is correct
15 Correct 20 ms 492 KB Output is correct
16 Correct 18 ms 492 KB Output is correct
17 Correct 19 ms 492 KB Output is correct
18 Correct 19 ms 492 KB Output is correct
19 Correct 380 ms 760 KB Output is correct
20 Correct 495 ms 876 KB Output is correct
21 Correct 314 ms 812 KB Output is correct
22 Correct 391 ms 748 KB Output is correct
23 Correct 330 ms 748 KB Output is correct
24 Correct 315 ms 748 KB Output is correct
25 Correct 306 ms 748 KB Output is correct
26 Correct 364 ms 748 KB Output is correct
27 Correct 292 ms 748 KB Output is correct
28 Correct 285 ms 876 KB Output is correct
29 Execution timed out 9080 ms 55276 KB Time limit exceeded
30 Halted 0 ms 0 KB -