結果

問題 No.3313 Matryoshka
コンテスト
ユーザー lif4635
提出日時 2025-10-24 22:56:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,011 bytes
コンパイル時間 2,957 ms
コンパイル使用メモリ 283,924 KB
実行使用メモリ 263,648 KB
最終ジャッジ日時 2025-10-24 22:56:22
合計ジャッジ時間 16,716 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:23:9: warning: #pragma once in main file
   23 | #pragma once
      |         ^~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map> // Pythonのdictに相当
#include <map>
#include <algorithm>
#include <queue>
#include <deque>
#include <set>
#include <iomanip> // std::setprecision

// C++の競プロ用標準テンプレート
using namespace std;

// 型エイリアス
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

#pragma once

template <typename Key, typename Val>
struct HashMap {
  using u32 = uint32_t;
  using u64 = uint64_t;

  u32 cap, s;
  vector<Key> keys;
  vector<Val> vals;
  vector<bool> flag;
  u64 r;
  u32 shift;
  Val DefaultValue;

  static u64 rng() {
    u64 m = chrono::duration_cast<chrono::nanoseconds>(
                chrono::high_resolution_clock::now().time_since_epoch())
                .count();
    m ^= m >> 16;
    m ^= m << 32;
    return m;
  }

  void reallocate() {
    cap <<= 1;
    vector<Key> k(cap);
    vector<Val> v(cap);
    vector<bool> f(cap);
    u32 sh = shift - 1;
    for (int i = 0; i < (int)flag.size(); i++) {
      if (flag[i]) {
        u32 hash = (u64(keys[i]) * r) >> sh;
        while (f[hash]) hash = (hash + 1) & (cap - 1);
        k[hash] = keys[i];
        v[hash] = vals[i];
        f[hash] = 1;
      }
    }
    keys.swap(k);
    vals.swap(v);
    flag.swap(f);
    --shift;
  }

  explicit HashMap()
      : cap(8),
        s(0),
        keys(cap),
        vals(cap),
        flag(cap),
        r(rng()),
        shift(64 - __lg(cap)),
        DefaultValue(Val()) {}

  Val& operator[](const Key& i) {
    u32 hash = (u64(i) * r) >> shift;
    while (true) {
      if (!flag[hash]) {
        if (s + s / 4 >= cap) {
          reallocate();
          return (*this)[i];
        }
        keys[hash] = i;
        flag[hash] = 1;
        ++s;
        return vals[hash] = DefaultValue;
      }
      if (keys[hash] == i) return vals[hash];
      hash = (hash + 1) & (cap - 1);
    }
  }

  // exist -> return pointer of Val
  // not exist -> return nullptr
  const Val* find(const Key& i) const {
    u32 hash = (u64(i) * r) >> shift;
    while (true) {
      if (!flag[hash]) return nullptr;
      if (keys[hash] == i) return &(vals[hash]);
      hash = (hash + 1) & (cap - 1);
    }
  }

  // return vector< pair<const Key&, val& > >
  vector<pair<Key, Val>> enumerate() const {
    vector<pair<Key, Val>> ret;
    for (u32 i = 0; i < cap; ++i)
      if (flag[i]) ret.emplace_back(keys[i], vals[i]);
    return ret;
  }

  int size() const { return s; }

  // set default_value
  void set_default(const Val& val) { DefaultValue = val; }
};

/**
 * @brief Hash Map(可変長版)
 * @docs docs/data-structure/hash-map.md
 */
template <typename S, typename T>
struct DynamicFenwickTree {
  S N;
  HashMap<S, T> data;
  explicit DynamicFenwickTree() = default;
  explicit DynamicFenwickTree(S size) { N = size + 1; }

  void add(S k, T x) {
    for (++k; k < N; k += k & -k) data[k] += x;
  }

  // [0, k)
  T sum(S k) const {
    if (k < 0) return 0;
    T ret = T();
    for (; k > 0; k -= k & -k) {
      const T* p = data.find(k);
      ret += p ? *p : T();
    }
    return ret;
  }

  // [a, b)
  T sum(S a, S b) const { return sum(b) - sum(a); }

  T operator[](S k) const { return sum(k + 1) - sum(k); }

  S lower_bound(T w) {
    if (w <= 0) return 0;
    S x = 0;
    for (S k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] < w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }
};

/**
 * @brief 動的Binary Indexed Tree
 * @docs docs/data-structure/dynamic-binary-indexed-tree.md
 */

template <typename T>
struct DynamicFenwickTree2D {
  using BIT = DynamicFenwickTree<int, T>;
  int N, M;
  vector<BIT*> bit;
  DynamicFenwickTree2D() = default;
  DynamicFenwickTree2D(int n, int m) : N(n + 1), M(m) {
    for (int _ = 0; _ < N; ++_) bit.push_back(new BIT(M));
  }
  
  void add(int i, int j, const T& x) {
    for (++i; i < N; i += i & -i) (*bit[i]).add(j, x);
  }

  // i = [0, n), j = [0, m)
  T sum(int n, int m) const {
    if (n < 0 || m < 0) return T();
    T ret = T();
    for (; n; n -= n & -n) ret += (*bit[n]).sum(m);
    return ret;
  }

  // i = [nl, nr), j = [ml, mr)
  T sum(int nl, int ml, int nr, int mr) const {
    T ret = T();
    while (nl != nr) {
      if (nl < nr) {
        ret += (*bit[nr]).sum(ml, mr);
        nr -= nr & -nr;
      } else {
        ret -= (*bit[nl]).sum(ml, mr);
        nl -= nl & -nl;
      }
    }
    return ret;
  }
};

/*
 * @brief 動的二次元Binary Indexed Tree
 */

int main() {
    // C++の入出力高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int lim = 1000000;
    int n;
    cin >> n;

    DynamicFenwickTree2D<int> bit(lim, lim);
    ll ans = 0;

    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        ans += bit.sum(l, lim - r);
        bit.add(l, lim - r, 1);
    }
    cout << ans << "\n";
    return 0;
}
0