#1186105 (C++23) No.3709 Unknown Treasure

• 問題: No.3709 Unknown Treasure
• ユーザー: kαmμ
• 提出日時: 2026-09-11 21:34:20
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 64 ms / 2,000 ms
• コード長: 10,341 bytes
• コンパイル時間: 2,195 ms
• コンパイル使用メモリ: 341,020 KB
• 実行使用メモリ: 19,200 KB
• 最終ジャッジ日時: 2026-09-11 21:34:34
• 合計ジャッジ時間: 5,488 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 36

ソースコード

#include <bits/stdc++.h>

#ifndef KAMMYU_CONSTANTS
#define KAMMYU_CONSTANTS

#include <limits>

namespace kammyu
{
  namespace infinities
  {
    constexpr int inf = std::numeric_limits<int>::max();
    constexpr int _inf = std::numeric_limits<int>::min();
    constexpr long long INF = std::numeric_limits<long long>::max();
    constexpr long long _INF = std::numeric_limits<long long>::min();
  }; // namespace infinities
  namespace modulos
  {
    constexpr int Smod = 998244353;
    constexpr int Bmod = 1000000007;
  }; // namespace modulos
}; // namespace kammyu

#endif // KAMMYU_CONSTANTS

#ifndef KAMMYU_INPUT
#define KAMMYU_INPUT

#include <iostream>
#include <iterator>
#include <utility>
#include <vector>

namespace kammyu
{
  namespace input
  {
    template <typename T1, typename T2>
    std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p)
    {
      return is >> p.first >> p.second;
    }

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

    template <typename T>
    void inp_arr(std::vector<T>& v)
    {
      for (T& i : v)
        std::cin >> i;
    }
    template <typename T1, typename T2>
    void inp_arr(std::vector<T1>& v1, std::vector<T2>& v2)
    {
      for (int i = 0; i < (int)v1.size(); i++)
        std::cin >> v1[i] >> v2[i];
    }
    template <typename T1, typename T2, typename T3>
    void inp_arr(std::vector<T1>& v1, std::vector<T2>& v2, std::vector<T3>& v3)
    {
      for (int i = 0; i < (int)v1.size(); i++)
        std::cin >> v1[i] >> v2[i] >> v3[i];
    }
    template <typename T1, typename T2, typename T3, typename T4>
    void inp_arr(std::vector<T1>& v1, std::vector<T2>& v2, std::vector<T3>& v3, std::vector<T4>& v4)
    {
      for (int i = 0; i < (int)v1.size(); i++)
        std::cin >> v1[i] >> v2[i] >> v3[i] >> v4[i];
    }
    template <typename T>
    void inp_arr(std::vector<std::vector<T>>& v)
    {
      for (std::vector<T>& i : v)
        for (T& j : i)
          std::cin >> j;
    }
  }; // namespace input
}; // namespace kammyu

#endif // KAMMYU_INPUT
#ifndef KAMMYU_OUTPUT
#define KAMMYU_OUTPUT

#include <iostream>
#include <ostream>
#include <vector>

namespace kammyu
{
  namespace output
  {
    template <typename T>
    std::ostream& operator<<(std::ostream& os, const std::vector<std::vector<T>>& v)
    {
      for (const std::vector<T>& x : v)
        os << x << "\n";
      return os;
    }
    template <typename T>
    std::ostream& operator<<(std::ostream& os, const std::vector<T>& v)
    {
      for (const T& x : v)
        os << x << " ";
      return os;
    }

    void yes(bool o = false)
    {
      if (o)
        std::cout << "Yes";
      else
        std::cout << "Yes" << std::endl;
    }
    void no(bool o = false)
    {
      if (o)
        std::cout << "No";
      else
        std::cout << "No" << std::endl;
    }
    void yn(bool b, bool o = false)
    {
      if (b)
        yes(o);
      else
        no(o);
    }
  }; // namespace output
}; // namespace kammyu

#endif // KAMMYU_OUTPUT

#ifndef KAMMYU_POINT
#define KAMMYU_POINT

#include <iostream>
#include <tuple>
#include <vector>

namespace kammyu
{
  namespace point
  {
    struct P
    {
    private:
      using ll = long long;

    public:
      P() { P(0, 0); }
      P(ll _i, ll _j) : i(_i), j(_j) {}
      ll i, j;
      bool operator==(const P& p) const { return i == p.i && j == p.j; }
      bool operator!=(const P& p) const { return !(*this == p); }
      bool operator<(const P& other) const { return std::tie(i, j) < std::tie(other.i, other.j); }
      bool operator>(const P& other) const { return std::tie(i, j) > std::tie(other.i, other.j); }
      P operator+(const P& other) const { return P(i + other.i, j + other.j); }
      P operator-(const P& other) const { return P(i - other.i, j - other.j); }
      P operator*(const int& other) const { return P(i * other, j * other); }
      P operator*(const ll& other) const { return P(i * other, j * other); }
      P operator*(const P& other) const { return P(i * other.i, j * other.j); }
      P operator*(const double& other) const { return P(i * other, j * other); }
      P operator/(const ll& scaler) const { return P(i / scaler, j / scaler); }
      P operator/(const double& scaler) const { return P(i / scaler, j / scaler); }
      P operator+=(const P& p) { return *this = *this + p; }
      P operator-=(const P& p) { return *this = *this - p; }
      P operator*=(const ll& p) { return *this = *this * p; }
      friend std::ostream& operator<<(std::ostream& os, const P& p) { return os << p.i << " " << p.j; }
      friend std::istream& operator>>(std::istream& is, P& p) { return is >> p.i >> p.j; }
      bool out_of_bounds(ll size) const { return i < 0 || j < 0 || i >= size || j >= size; }
      bool out_of_bounds(ll H, ll W) const { return i < 0 || j < 0 || i >= H || j >= W; }
      P& operator--()
      {
        --i, --j;
        return *this;
      }
      P operator--(int)
      {
        P p = *this;
        --(*this);
        return p;
      }
      void swap()
      {
        std::swap(i, j);
      }
      ll distEucSq() const { return i * i + j * j; }
      ll distManh() const { return i + j; }
    };

    using piP = std::pair<int, P>;
    using pPP = std::pair<P, P>;
    using vP = std::vector<P>;
    using vpiP = std::vector<piP>;
    using vpPP = std::vector<pPP>;
    using vvP = std::vector<std::vector<P>>;
    using vvpiP = std::vector<std::vector<piP>>;
    const vP around4({P(0, 1), P(1, 0), P(0, -1), P(-1, 0)});
    const vP around8({P(0, 1), P(1, 1), P(1, 0), P(1, -1), P(0, -1), P(-1, -1), P(-1, 0), P(-1, 1)});
  }; // namespace point
}; // namespace kammyu

#endif // KAMMYU_POINT

#ifndef KAMMYU_UTILS
#define KAMMYU_UTILS

#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, s, e) for (int i = (s); i < (e); ++i)
#define reep(i, n) for (int i = 0; i <= (n); ++i)
#define reepp(i, s, e) for (int i = (s); i <= (e); ++i)
#define rrep(i, n) for (int i = (n - 1); i >= 0; --i)
#define rrepp(i, s, e) for (int i = (e - 1); i >= s; --i)
#define sign(f) (f == 0 ? 0 : ((f) > 0) * 2 - 1)

#define pqueue priority_queue

namespace kammyu
{

  namespace utils
  {
    template <typename T1, typename T2>
    bool chmax(T1& m, const T2& val)
    {
      if (m < val)
      {
        m = val;
        return true;
      }
      return false;
    }
    template <typename T1, typename T2>
    bool chmin(T1& m, const T2& val)
    {
      if (m > val)
      {
        m = val;
        return true;
      }
      return false;
    }

    using ll = long long;
    using pii = std::pair<int, int>;
    using piii = std::pair<int, pii>;
    using si = std::set<int>;
    using vi = std::vector<int>;
    using vpii = std::vector<pii>;
    using vpiii = std::vector<piii>;
    using vvi = std::vector<std::vector<int>>;
    using vvpii = std::vector<std::vector<pii>>;
    using vvvi = std::vector<vvi>;
    using vvvvi = std::vector<vvvi>;

    using vb = std::vector<bool>;
    using vvb = std::vector<vb>;
    using pli = std::pair<ll, int>;
    using plii = std::pair<pli, int>;
    using vpli = std::vector<pli>;
    using vvpli = std::vector<std::vector<pli>>;

    using pll = std::pair<ll, ll>;
    using plll = std::pair<pll, ll>;
    using vl = std::vector<ll>;
    using vpll = std::vector<pll>;
    using vvl = std::vector<std::vector<ll>>;
    using vvpll = std::vector<std::vector<pll>>;
    using vvvl = std::vector<vvl>;
    using vvvvl = std::vector<vvvl>;

    using vsi = std::vector<std::set<int>>;

    using vs = std::vector<std::string>;
    template <typename T>
    using vv = std::vector<std::vector<T>>;

    template <typename T>
    using min_pqueue = std::priority_queue<T, std::vector<T>, std::greater<T>>;
    template <typename T>
    using max_pqueue = std::priority_queue<T>;

    template <typename T1, typename T2>
    std::pair<T1, T2> operator+(const std::pair<T1, T2>& a, const std::pair<T1, T2>& b)
    {
      return std::make_pair(a.first + b.first, a.second + b.second);
    }
    template <typename T1, typename T2>
    std::pair<T1, T2> operator-(const std::pair<T1, T2>& a, const std::pair<T1, T2>& b)
    {
      return std::make_pair(a.first - b.first, a.second - b.second);
    }

    template <typename T>
    void sort(std::vector<T>& v)
    {
      std::sort(all(v));
    }

    vi str2vi(const std::string& s, char first_char = 'a')
    {
      vi res(s.size());
      rep(i, s.size()) res[i] = s[i] - first_char;
      return res;
    }

    template <typename T>
    T sum(const std::vector<T>& vec)
    {
      T res = T();
      for (const T& val : vec)
        res = res + val;
      return res;
    }
    template <typename T>
    T min(const std::vector<T>& vec, T init)
    {
      T res = init;
      for (const T& val : vec)
        if (val < res)
          res = val;
      return res;
    }
    template <typename T>
    T max(const std::vector<T>& vec, T init)
    {
      T res = init;
      for (const T& val : vec)
        if (val > res)
          res = val;
      return res;
    }

  }; // namespace utils
}; // namespace kammyu

#endif // KAMMYU_UTILS


using namespace kammyu::utils;
using namespace kammyu::input;
using namespace kammyu::output;
using namespace kammyu::point;

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

  MAIN();

  return 0;
}

using namespace std;
void solve();
void precalc();
void MAIN()
{
  precalc();
  int T = 1;
  // cin >> T;
  while (T--)
    solve();

  return;
}

// using namespace kammyu::infinities;
// using namespace kammyu::modulos;
void precalc()
{
  return;
}
void solve()
{
  int H, W, N;
  cin >> H >> W >> N;

  vvi no(H + 2, vi(W + 2, 0));
  while (N--)
  {
    P l, r;
    cin >> l >> r;
    r.i++, r.j++;
    no[l.i][l.j]++, no[l.i][r.j]--, no[r.i][l.j]--, no[r.i][r.j]++;
  }

  int ans = 0;
  rep(i, H) rep(j, W)
  {
    no[i + 1][j + 1] += no[i][j + 1] + no[i + 1][j] - no[i][j];
    if (no[i + 1][j + 1] == 0)
      ans++;
  }
  cout << ans << endl;

  return;
}