結果
| 問題 | No.3709 Unknown Treasure |
| コンテスト | |
| ユーザー |
 fepic_
|
| 提出日時 | 2026-09-11 21:37:29 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 82 ms / 2,000 ms |
| + 769µs | |
| コード長 | 10,532 bytes |
| 記録 | |
| コンパイル時間 | 2,993 ms |
| コンパイル使用メモリ | 278,788 KB |
| 実行使用メモリ | 34,816 KB |
| 最終ジャッジ日時 | 2026-09-11 21:38:37 |
| 合計ジャッジ時間 | 7,010 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
//-------------------------------------------------------------------------------------
/*
8 4 2 1以上の形でないといけない
*/
//-------------------------------------------------------------------------------------
// unordered_set
//__builtin_popcountll
//./a.out < in.txt > out.txt
// g++ -std=gnu++23 -O0 -g0 -pipe -I. a.cpp
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG //[]で配列外参照をするとエラーにしてくれる。上下のやつがないとTLEになるので注意 ABC311Eのサンプル4みたいなデバック中のTLEは防げないので注意
#endif
// #include <boost/multiprecision/cpp_int.hpp>
// namespace boo = boost::multiprecision;
using mint = modint1000000007;
// 1000000007
// 998244353
using pll = pair<long long, long long>;
typedef long long ll;
typedef long double ld;
// #define _GLIBCXX_DEBUG
#define INF (ll)2e18
#define fi first
#define se second
#define R return 0
#define PB push_back
#define stirng string
#define vll vector<ll>
#define mutliset multiset
#define NO cout << "No" << endl
#define YES cout << "Yes" << endl
#define ANS cout << ans << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dou fixed << setprecision(20)
#define an cout << (ans ? "Yes" : "No")
#define en cout << "------------" << endl
// #define min(x,y) ((x) < (y) ? (x) : (y))
// #define max(x,y) ((x) > (y) ? (x) : (y))
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define vv(name, h, w, type, init) \
std::vector<std::vector<type>> name((h), std::vector<type>((w), (init)))
#define vvv(name, d, h, w, type, init) \
std::vector<std::vector<std::vector<type>>> name((d), \
std::vector<std::vector<type>>((h), std::vector<type>((w), (init))))
#define vvvv(name, x, y, z, w, type, init) \
std::vector<std::vector<std::vector<std::vector<type>>>> name((x), \
std::vector<std::vector<std::vector<type>>>((y), \
std::vector<std::vector<type>>((z), std::vector<type>((w), (init)))))
#define vvvvv(name, a, b, c, d, e, type, init) \
std::vector<std::vector<std::vector<std::vector<std::vector<type>>>>> name( \
(a), std::vector<std::vector<std::vector<std::vector<type>>>>( \
(b), std::vector<std::vector<std::vector<type>>>( \
(c), std::vector<std::vector<type>>( \
(d), std::vector<type>((e), (init))))))
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
long long TEN(int x) { return x == 0 ? 1 : TEN(x - 1) * 10; }
template <typename T>
constexpr std::pair<T, T> myminmax(const T& a, const T& b) {
// 比較に基づいて {min, max} を直接組み立てて返す
return (b < a) ? std::pair{b, a} : std::pair{a, b};
}
template <class T>
inline bool chmax(T &a, T b)
{
if (a < b)
{
a = b;
return 1;
}
return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
if (a > b)
{
a = b;
return 1;
}
return 0;
}
template <typename T>
auto rle(const T& v) {
using val_t = typename T::value_type;
std::vector<std::pair<val_t, ll>> res;
for (const auto& elem : v) {
if (res.empty() || res.back().first != elem) {
res.emplace_back(elem, 1);
} else {
res.back().second++;
}
}
return res;
}
// ll mod = (ll)1000000007;
ll mod = (ll)998244353;
// ll inv = 499122177;
vector<ll> f1 = {0, -1, 0, 1}, f2 = {-1, 0, 1, 0}; // 四方向
vector<ll> f3 = {-1, 0, 1, 0, 1, -1, 1, -1}, f4 = {0, 1, 0, -1, 1, 1, -1, -1}; // ハチ方向
template <class T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template <class T>
long long reduce(const vector<T> &a)
{
long long s = 0;
for (auto &x : a)
s += x;
return s;
}
void yn(bool ok)
{
cout << (ok ? "Yes" : "No") << '\n';
}
#define yu_qurid(x, y) ((x) * (x) + (y) * (y)) // ユークリッド距離 sqrtはしてないなので注意
#define mannhattan(x1, x2, y1, y2) (abs(x1 - x2) + abs(y1 - y2)) // マンハッタン距離 = |x1-x2|+|y1-y2|
// reference @frest
#define vc_cout(v) \
do \
{ \
ll nn = v.size(); \
for (int i = 0; i < nn; i++) \
{ \
cout << v[i] << " "; \
} \
cout << endl; \
} while (0)
#define vv_cout(v) \
do \
{ \
ll nn = v.size(); \
for (int i = 0; i < nn; i++) \
{ \
for (int j = 0; j < v[i].size(); j++) \
cout << v[i][j] << " "; \
cout << endl; \
} \
} while (0)
// n(10進数)をa進数に
string to_oct(ll n, ll a)
{
string s;
while (n)
{
s = to_string(n % a) + s;
n /= a;
}
return s;
}
bool bfs_est(ll xx1, ll yy1, ll hhh, ll www)
{
return (0 <= xx1 && xx1 < hhh && 0 <= yy1 && www > yy1);
}
static const auto fast_io = []()
{
cin.tie(nullptr);
ios::sync_with_stdio(false);
return 0;
}();
ll e(){
return 0;
}
ll op(ll a, ll b){
return a+b;
}
bool IsPrime(int num) // 素数判定
{
if (num < 2)
return false;
else if (num == 2)
return true;
else if (num % 2 == 0)
return false;
double sqrtNum = sqrt(num);
for (int i = 3; i <= sqrtNum; i += 2)
{
if (num % i == 0)
{
return false;
}
}
// 素数である
return true;
}
template <typename T, size_t N>
class NDPrefixSum {
private:
std::array<long long, N> shape;
std::array<long long, N> strides;
std::vector<T> data;
bool is_built;
void compute_strides() {
long long prod = 1;
for (long long i = static_cast<long long>(N) - 1; i >= 0; --i) {
strides[i] = prod;
prod *= shape[i];
}
}
void accumulate_along_dim(long long current_dim, long long target_dim, std::array<long long, N>& indices) {
if (current_dim == static_cast<long long>(N)) {
long long base_idx = 0;
for (long long i = 0; i < static_cast<long long>(N); ++i) {
if (i != target_dim) {
base_idx += indices[i] * strides[i];
}
}
for (long long i = 1; i < shape[target_dim]; ++i) {
long long prev_idx = base_idx + (i - 1) * strides[target_dim];
long long curr_idx = base_idx + i * strides[target_dim];
data[curr_idx] += data[prev_idx];
}
return;
}
if (current_dim == target_dim) {
indices[current_dim] = 0;
accumulate_along_dim(current_dim + 1, target_dim, indices);
} else {
for (long long i = 0; i < shape[current_dim]; ++i) {
indices[current_dim] = i;
accumulate_along_dim(current_dim + 1, target_dim, indices);
}
}
}
void query_recursive(long long dim, const std::array<long long, N>& low, const std::array<long long, N>& high,
std::array<long long, N>& current_idx, bool positive, T& sum) const {
if (dim == static_cast<long long>(N)) {
long long idx = 0;
for (long long i = 0; i < static_cast<long long>(N); ++i) {
idx += current_idx[i] * strides[i];
}
if (positive) {
sum += data[idx];
} else {
sum -= data[idx];
}
return;
}
current_idx[dim] = high[dim];
query_recursive(dim + 1, low, high, current_idx, positive, sum);
if (low[dim] > 0) {
current_idx[dim] = low[dim] - 1;
query_recursive(dim + 1, low, high, current_idx, !positive, sum);
}
}
public:
explicit NDPrefixSum(const std::array<long long, N>& shape) : shape(shape), is_built(false) {
compute_strides();
long long total_size = 1;
for (long long s : shape) {
total_size *= s;
}
data.assign(total_size, T(0));
}
void set(const std::array<long long, N>& indices, const T& value) {
assert(!is_built);
long long idx = 0;
for (long long i = 0; i < static_cast<long long>(N); ++i) {
assert(indices[i] >= 0 && indices[i] < shape[i]);
idx += indices[i] * strides[i];
}
data[idx] = value;
}
void build() {
if (is_built) return;
std::array<long long, N> indices{};
for (long long d = 0; d < static_cast<long long>(N); ++d) {
accumulate_along_dim(0, d, indices);
}
is_built = true;
}
T query(const std::array<long long, N>& low, const std::array<long long, N>& high) const {
assert(is_built);
for (long long i = 0; i < static_cast<long long>(N); ++i) {
assert(low[i] <= high[i]);
assert(high[i] < shape[i]);
}
T sum = T(0);
std::array<long long, N> current_idx{};
query_recursive(0, low, high, current_idx, true, sum);
return sum;
}
};
int main() {
ll h,w,n;
cin>>h>>w>>n;
vv(imos,h+1,w+1,ll,0);
rep(i,n){
ll a,b,c,d;
cin>>a>>b>>c>>d;
a--;b--;c--;d--;
imos[a][b]++;
imos[c+1][b]--;
imos[a][d+1]--;
imos[c+1][d+1]++;
}
rep(i,h){
rep(j,w){
imos[i+1][j] += imos[i][j];
}
}
rep(i,h){
rep(j,w){
imos[i][j+1] += imos[i][j];
}
}
ll ans = 0;
rep(i,h){
rep(j,w){
ans += (imos[i][j] == 0);
}
}
ANS;
}