結果

問題 No.728 ギブ and テイク
コンテスト
ユーザー とばり
提出日時 2018-09-02 14:09:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 217 ms / 3,000 ms
コード長 3,477 bytes
コンパイル時間 1,719 ms
コンパイル使用メモリ 180,204 KB
実行使用メモリ 26,848 KB
最終ジャッジ日時 2024-10-01 06:40:46
合計ジャッジ時間 6,197 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
using uint64 = unsigned long long;

#define repeat(i, x) for (int64 i = 0; (i) < (x); (i)++)
#define rev_repeat(i, x) for (int64 i = (x) - 1; (i) >= 0; (i)--)
#define countup(i, n) for (int64 i = 0; (i) <= (n); (i)++)
#define countdown(i, n) for (int64 i = (n); (i) >= 0; (i)--)
#define range(i, a, b) for (int64 i = (a); (i) < (b); (i)++)
#define traverse(it, ctn) for (auto it = begin(ctn); (it) != end(ctn); (it)++)
#define rev_traverse(it, ctn) for (auto it = rbegin(ctn); (it) != rend(ctn); (it)++)

template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec)
{
    os << "[";
    repeat (i, vec.size())
    {
        os << (i == 0 ? "" : ", ") << vec[i];
    }
    os << "]";
    return os;
}

template<typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& p)
{
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template<typename T>
ostream& operator<<(ostream& os, set<T>& s)
{
    os << "{";
    traverse (it, s)
    {
        if (it != s.begin()) os << ", ";
        os << *it;
    }
    os << "}";
    return os;
}

template<typename K, typename V>
ostream& operator<<(ostream& os, map<K, V>& m) 
{
    os << "{";
    traverse (it, m)
    {
        if (it != m.begin()) os << ", ";
        os << it->first << ": " << it->second;
    }
    os << "}";
    return os;
}

//
// _______  _____  _______  _____  _______ _______ _____ _______ _____ _    _ _______ 
// |       |     | |  |  | |_____] |______    |      |      |      |    \  /  |______ 
// |_____  |_____| |  |  | |       |______    |    __|__    |    __|__   \/   |______ 
//
//  _____   ______  _____   ______  ______ _______ _______ _______ _____ __   _  ______   /
// |_____] |_____/ |     | |  ____ |_____/ |_____| |  |  | |  |  |   |   | \  | |  ____  / 
// |       |    \_ |_____| |_____| |    \_ |     | |  |  | |  |  | __|__ |  \_| |_____| .  
//

using Event = tuple<int64, int, int>;   // (座標, イベントの種類, Aにおける添字)

template <class T>
struct fenwick_tree {
    int n;
    std::vector<T> x;
    fenwick_tree(int n_ = 0) : n(n_), x(n + 1, 0) {}
    int size() const { return n; }
    T sum(int r) const {
        T S = 0;
        for (r = r - 1; r >= 0; r = (r & (r + 1)) - 1) S += x[r];
        return S;
    }
    T sum(int l, int r) const { return sum(r) - sum(l); }
    void add(int k, const T &a) {
        for (; k < n; k |= k + 1) x[k] += a;
    }
    void set(int k, const T &a) { add(k, a - sum(k, k + 1)); }
};

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    vector<int64> A(N);
    repeat (i, N)
    {
        cin >> A[i];
    }

    vector<int64> L(N), R(N);
    vector<Event> events;   // (座標、イベントの種類)
    repeat (i, N)
    {
        cin >> L[i] >> R[i];

        events.emplace_back(A[i] - L[i], 0, i);
        events.emplace_back(A[i], 1, i);
    }

    sort(events.begin(), events.end());

    fenwick_tree<int64> ft(N);

    int64 ans = 0;
    for (auto& ev : events)
    {
        int idx = get<2>(ev);

        if (get<1>(ev) == 0)
        {
            ft.add(idx, 1);
        }
        else
        {
            // A[k] <= A[i] + R[i]を満たす最大のkを見つける
            int k = (upper_bound(A.begin(), A.end(), A[idx] + R[idx]) - A.begin()) - 1;
            ans += ft.sum(idx + 1, k + 1);
        }
    }

    cout << ans << endl;

    return 0;
}
0