#877479 (C++17) No.2338 Range AtCoder Query

提出ソース

結果

問題	No.2338 Range AtCoder Query
ユーザー	rniya
提出日時	2023-06-02 23:17:44
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	5,396 bytes
コンパイル時間	3,195 ms
コンパイル使用メモリ	222,592 KB
実行使用メモリ	32,088 KB
最終ジャッジ日時	2024-06-09 01:23:21
合計ジャッジ時間	10,103 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 10,752 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	4 ms 5,376 KB
testcase_07	AC	4 ms 5,376 KB
testcase_08	AC	4 ms 5,376 KB
testcase_09	AC	4 ms 5,376 KB
testcase_10	AC	4 ms 5,376 KB
testcase_11	TLE	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

struct Mo {
    Mo(int n) : n(n) {}

    void add(int l, int r) {
        assert(l <= r);
        left.emplace_back(l);
        right.emplace_back(r);
    }

    template <typename AL, typename AR, typename DL, typename DR, typename REM>
    void run(const AL& add_left, const AR& add_right, const DL& del_left, const DR del_right, const REM& rem) {
        int q = left.size(), width = n / std::min(std::max<int>(sqrt(q * 2 / 3), 1), n);
        std::vector<int> order(q);
        std::iota(order.begin(), order.end(), 0);
        std::sort(order.begin(), order.end(), [&](int a, int b) {
            int ablock = left[a] / width, bblock = left[b] / width;
            if (ablock != bblock) return ablock < bblock;
            return (ablock & 1) ? (right[a] > right[b]) : (right[a] < right[b]);
        });

        int l = 0, r = 0;
        for (auto idx : order) {
            while (l > left[idx]) add_left(--l);
            while (r < right[idx]) add_right(r++);
            while (l < left[idx]) del_left(l++);
            while (r > right[idx]) del_right(--r);
            rem(idx);
        }
    }

    template <typename A, typename D, typename REM> void run(const A& add, const D& del, const REM& rem) {
        run(add, add, del, del, rem);
    }

private:
    int n;
    std::vector<int> left, right;
};

template <typename T> struct BinaryIndexedTree {
    BinaryIndexedTree() : n(0) {}
    BinaryIndexedTree(int n) : n(n), data(n) {}

    void add(int k, T x) {
        assert(0 <= k && k < n);
        for (k++; k <= n; k += k & -k) data[k - 1] += x;
    }

    T query(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        return sum(r) - sum(l);
    }

    T operator[](int i) const { return query(i, i + 1); }

    int lower_bound(T x) const {
        if (x <= 0) return 0;
        int cur = 0, k = 1;
        while (k < n) k <<= 1;
        for (; k > 0; k >>= 1) {
            if (cur + k <= n && data[cur + k - 1] < x) {
                x -= data[cur + k - 1];
                cur += k;
            }
        }
        return cur;
    }
    int upper_bound(T x) const { return lower_bound(x + 1); }

  private:
    int n;
    std::vector<T> data;

    T sum(int r) const {
        T res = 0;
        for (; r > 0; r -= r & -r) res += data[r - 1];
        return res;
    }
};

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> P(N), S(N);
    for (int i = 0; i < N; i++) {
        string tmp;
        cin >> P[i] >> tmp;
        P[i]--;
        S[i] = (tmp == "AC");
    }

    Mo mo(N);
    for (int i = 0; i < Q; i++) {
        int L, R;
        cin >> L >> R;
        mo.add(--L, R);
    }
    vector<vector<int>> cand(M);
    for (int i = 0; i < N; i++) cand[P[i]].emplace_back(i);
    vector<BinaryIndexedTree<int>> ac(M), wa(M);
    vector<int> ord(N);
    for (int i = 0; i < N; i++) ord[i] = lwb(cand[P[i]], i);
    for (int i = 0; i < M; i++) {
        ac[i] = BinaryIndexedTree<int>(cand[i].size());
        wa[i] = BinaryIndexedTree<int>(cand[i].size());
    }
    int correct = 0, penalty = 0;
    auto calc = [&](int idx) {
        if (ac[idx].query(0, cand[idx].size()) == 0) return 0;
        int x = ac[idx].lower_bound(1);
        return wa[idx].query(0, x);
    };
    auto add = [&](int idx) {
        int x = P[idx];
        {
            correct -= (ac[x].query(0, cand[x].size()) > 0);
            penalty -= calc(x);
        }
        if (S[idx] == 0)
            wa[x].add(ord[idx], 1);
        else
            ac[x].add(ord[idx], 1);
        {
            correct += (ac[x].query(0, cand[x].size()) > 0);
            penalty += calc(x);
        }
    };
    auto del = [&](int idx) {
        int x = P[idx];
        {
            correct -= (ac[x].query(0, cand[x].size()) > 0);
            penalty -= calc(x);
        }
        if (S[idx] == 0)
            wa[x].add(ord[idx], -1);
        else
            ac[x].add(ord[idx], -1);
        {
            correct += (ac[x].query(0, cand[x].size()) > 0);
            penalty += calc(x);
        }
    };
    vector<int> ans1(Q), ans2(Q);
    auto rem = [&](int idx) {
        ans1[idx] = correct;
        ans2[idx] = penalty;
    };

    mo.run(add, del, rem);
    for (int i = 0; i < Q; i++) cout << ans1[i] << ' ' << ans2[i] << '\n';
    return 0;
}

yukicoder

結果

テストケース

ソースコード