結果

問題 No.956 Number of Unbalanced
ユーザー square1001
提出日時 2019-12-19 00:19:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,194 bytes
コンパイル時間 901 ms
コンパイル使用メモリ 85,056 KB
実行使用メモリ 14,252 KB
最終ジャッジ日時 2024-07-06 23:04:29
合計ジャッジ時間 4,616 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifndef CLASS_FENWICKTREE
#define CLASS_FENWICKTREE
#include <cstddef>
template <class type>
class fenwick_tree {
private:
    std::size_t n, sz;
    type* val;
public:
    fenwick_tree() : n(0), sz(0) {};
    fenwick_tree(std::size_t n_) : n(n_) {
        sz = 1; while (sz < n) sz *= 2;
        val = new type[sz + 1]();
    }
    template <class InputIterator>
    fenwick_tree(InputIterator first, InputIterator last) : n(last - first) {
        sz = 1; while (sz < n) sz *= 2;
        val = new type[sz + 1]();
        std::size_t cur = 0;
        for (InputIterator it = first; it != last; ++it) val[++cur] += *it;
        for (std::size_t i = 1; i < sz; ++i) val[i + (i & ~(i - 1))] += val[i];
    }
    ~fenwick_tree() { delete[] val; }
    void add(std::size_t pos, type delta) {
        for (std::size_t i = pos + 1; i <= sz; i += i & ~(i - 1)) {
            val[i] += delta;
        }
    }
    type getsum(std::size_t r) const {
        type ans = 0;
        for (std::size_t i = r; i >= 1; i -= i & ~(i - 1)) {
            ans += val[i];
        }
        return ans;
    }
    type getsum(std::size_t l, std::size_t r) const {
        return getsum(r) - getsum(l);
    }
    std::size_t binary_search(type threshold) const {
        std::size_t ans = 0;
        for (std::size_t i = sz / 2; i >= 1; i >>= 1) {
            if (threshold >= val[ans + i]) {
                threshold -= val[ans + i];
                ans += i;
            }
        }
        return ans;
    }
};
#endif // CLASS_FENWICKTREE
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    vector<int> SA = A;
    sort(SA.begin(), SA.end());
    SA.erase(unique(SA.begin(), SA.end()), SA.end());
    int S = SA.size();
    for (int i = 0; i < N; ++i) {
        A[i] = lower_bound(SA.begin(), SA.end(), A[i]) - SA.begin();
    }
    vector<vector<int> > G(S);
    for (int i = 0; i < N; ++i) {
        G[A[i]].push_back(i);
    }
    long long ans = 0;
    for (int i = 0; i < S; ++i) {
        int M = G[i].size();
        vector<int> l(M), r(M);
        for (int j = 0; j < M; ++j) {
            l[j] = max(G[i][j] - 2 * M + 2, 0);
            r[j] = min(G[i][j] + 2 * M, N + 1);
        }
        vector<int> cp;
        cp.insert(cp.begin(), l.begin(), l.end());
        cp.insert(cp.begin(), r.begin(), r.end());
        sort(cp.begin(), cp.end());
        cp.erase(unique(cp.begin(), cp.end()), cp.end());
        vector<int> sum(cp.size());
        for (int j = 0; j < M; ++j) {
            l[j] = lower_bound(cp.begin(), cp.end(), l[j]) - cp.begin();
            r[j] = lower_bound(cp.begin(), cp.end(), r[j]) - cp.begin();
            ++sum[l[j]];
            --sum[r[j]];
        }
        for (int j = 1; j < cp.size(); ++j) {
            sum[j] += sum[j - 1];
        }
        int lp = -1;
        for (int j = 0; j < cp.size(); ++j) {
            if (sum[j] >= 1 && lp == -1) {
                lp = j;
            }
            else if (sum[j] == 0 && lp != -1) {
                vector<int> seq;
                for (int k = cp[lp]; k < cp[j]; ++k) {
                    seq.push_back(2 * (lower_bound(G[i].begin(), G[i].end(), k) - G[i].begin()) - k);
                }
                int mn = *min_element(seq.begin(), seq.end());
                for (int k = 0; k < seq.size(); ++k) {
                    seq[k] -= mn;
                }
                int mx = *max_element(seq.begin(), seq.end());
                fenwick_tree<int> bit(mx + 1);
                for (int k = 0; k < seq.size(); ++k) {
                    ans += bit.getsum(seq[k]);
                    bit.add(seq[k], 1);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0