結果

問題 No.1371 交換門松列・松
コンテスト
ユーザー carrot46
提出日時 2021-02-09 16:39:59
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 68 ms / 4,000 ms
コード長 2,881 bytes
コンパイル時間 1,674 ms
コンパイル使用メモリ 179,072 KB
実行使用メモリ 8,800 KB
最終ジャッジ日時 2024-07-06 22:33:11
合計ジャッジ時間 4,312 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <chrono>
//#pragma GCC optimize("Ofast")
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()

using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

ll N,M,H,W,Q,K,A,B;
string S;
using P = pair<ll, ll>;
const ll INF = (1LL<<60);

template<class T> bool chmin(T &a, const T b){
    if(a > b) {a = b; return true;}
    else return false;
}
template<class T> bool chmax(T &a, const T b){
    if(a < b) {a = b; return true;}
    else return false;
}
template<class T> void my_printv(std::vector<T> v,bool endline = true){
    if(!v.empty()){
        for(std::size_t i{}; i<v.size()-1; ++i) std::cout<<v[i]<<" ";
        std::cout<<v.back();
    }
    if(endline) std::cout<<std::endl;
}

template <class T> class BIT {
    //T has operator "+=" and can be initialized with 0.
    unsigned int n;
    vector<T> bitree;
public:
    BIT(unsigned long _n) : bitree(_n + 1, 0) {
        n = _n;
    }

    void add(int id, T x) {
        ++id;
        while (id <= n) {
            bitree[id] += x;
            id += id & -id;
        }
    }

    T sum(int id) {
        ++id;
        T temp(0);
        while (id > 0) {
            temp += bitree[id];
            id -= id & -id;
        }
        return temp;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>N;
    vec a(N + 2);
    vector<P> low, high;
    reps(i, 1, N + 1) cin>>a[i];
    a[0] = (a[1] > a[2] ? 0 : N + 1);
    a[N+1] = (a[N-1] < a[N] ? 0 : N + 1);
    reps(i, 1, N + 1){
        if(a[i] < a[i+1]) low.emplace_back(a[i], min(a[i-1], a[i+1]));
        else high.emplace_back(a[i], max(a[i-1], a[i+1]));
    }
    ll res = 0;

    sort(ALL(low));
    {
        BIT<int> bit(N + 10);
        for (P p : low) {
            res += bit.sum(N + 5) - bit.sum(p.first);
            bit.add(p.second, 1);
        }
    }

    sort(ALL(high)); reverse(ALL(high));
    {
        BIT<int> bit(N + 10);
        for(P p : high){
            res += bit.sum(p.first);
            bit.add(p.second, 1);
        }
    }

    reverse(ALL(high));
    BIT<int> bit(N + 10);
    for(P &p : low) {
        swap(p.first, p.second);
        bit.add(p.second, 1);
    }
    sort(ALL(low));
    int lsz = low.size(), hsz = high.size();
    int i{}, j{};
    const P inf(INF, INF);
    while(i < lsz || j < hsz){
        P p = inf, q = inf;
        if(i < lsz) p = low[i];
        if(j < hsz) q = high[j];
        if(p.first < q.first){
            bit.add(p.second, -1);
            ++i;
        }else{
            //cout<<i<<' '<<j<<' '<< bit.sum(N + 5) - bit.sum(q.second)<<endl;
            res += bit.sum(N + 5) - bit.sum(q.second);
            ++j;
        }
    }
    cout<<res<<endl;
}
0