結果

問題 No.1505 Zero-Product Ranges
ユーザー CyanmondCyanmond
提出日時 2021-05-14 23:06:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 2,718 bytes
コンパイル時間 2,174 ms
コンパイル使用メモリ 194,552 KB
最終ジャッジ日時 2025-01-21 12:05:07
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,824 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 35 ms
6,816 KB
testcase_04 AC 37 ms
6,820 KB
testcase_05 AC 15 ms
6,816 KB
testcase_06 AC 14 ms
6,820 KB
testcase_07 AC 11 ms
6,816 KB
testcase_08 AC 13 ms
6,820 KB
testcase_09 AC 12 ms
6,820 KB
testcase_10 AC 13 ms
6,820 KB
testcase_11 AC 16 ms
6,824 KB
testcase_12 AC 13 ms
6,820 KB
testcase_13 AC 23 ms
6,820 KB
testcase_14 AC 19 ms
6,820 KB
testcase_15 AC 34 ms
6,820 KB
testcase_16 AC 37 ms
6,816 KB
testcase_17 AC 38 ms
6,820 KB
testcase_18 AC 38 ms
6,820 KB
testcase_19 AC 2 ms
6,816 KB
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 2 ms
6,820 KB
testcase_22 AC 39 ms
6,816 KB
testcase_23 AC 39 ms
6,816 KB
testcase_24 AC 35 ms
6,820 KB
testcase_25 AC 34 ms
6,820 KB
testcase_26 AC 35 ms
6,824 KB
testcase_27 AC 34 ms
6,820 KB
testcase_28 AC 37 ms
6,820 KB
testcase_29 AC 39 ms
6,816 KB
testcase_30 AC 40 ms
6,816 KB
testcase_31 AC 37 ms
6,820 KB
testcase_32 AC 21 ms
6,816 KB
testcase_33 AC 19 ms
6,820 KB
testcase_34 AC 21 ms
6,820 KB
testcase_35 AC 16 ms
6,820 KB
testcase_36 AC 16 ms
6,816 KB
testcase_37 AC 20 ms
6,820 KB
testcase_38 AC 19 ms
6,820 KB
testcase_39 AC 19 ms
6,816 KB
testcase_40 AC 20 ms
6,820 KB
testcase_41 AC 22 ms
6,820 KB
testcase_42 AC 4 ms
6,816 KB
testcase_43 AC 5 ms
6,816 KB
testcase_44 AC 4 ms
6,820 KB
testcase_45 AC 5 ms
6,824 KB
testcase_46 AC 3 ms
6,820 KB
testcase_47 AC 5 ms
6,820 KB
testcase_48 AC 4 ms
6,820 KB
testcase_49 AC 2 ms
6,820 KB
testcase_50 AC 4 ms
6,820 KB
testcase_51 AC 4 ms
6,824 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include "bits/stdc++.h"
#pragma region header
#define loop(n) for ([[maybe_unused]] size_t lpcnt_ = 0; lpcnt_ < (n); ++lpcnt_)
using i32 = int;
using i64 = long long int;
using u32 = unsigned int;
using u64 = unsigned long long int;
using isize = ptrdiff_t;
using usize = size_t;
constexpr usize operator"" _uz(u64 v) { return usize(v); }
inline u64 popcount(const u64 v) {
#ifdef _MSC_VER
return u64(__popcnt64(v));
#else
return u64(__builtin_popcount(v));
#endif
}
class range {
struct range_iterator {
usize itr;
constexpr range_iterator(const usize pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept { ++itr; }
constexpr bool operator!=(const range_iterator& other) const noexcept {
return itr != other.itr;
}
constexpr usize operator*() const noexcept { return itr; }
};
const range_iterator first, last;
public:
explicit constexpr range(const usize first_, const usize last_) noexcept
: first(first_), last(last_) {}
constexpr range_iterator begin() const noexcept { return first; }
constexpr range_iterator end() const noexcept { return last; }
};
template <class F>
class rec_lambda {
F f;
public:
constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
template <class... Args>
constexpr auto operator()(Args&&... args) const {
return f(*this, std::forward<Args>(args)...);
}
};
namespace cs_helper {
void zip_sort_renumber([[maybe_unused]] const std::vector<usize>& order) {}
template <class T, class... Args>
void zip_sort_renumber(const std::vector<usize>& order, std::vector<T>& head,
Args&... args) {
usize n = order.size();
assert(n == head.size());
std::vector<T> sorted_head(n);
for (usize i = 0; i < n; ++i) sorted_head[i] = head[order[i]];
head = std::move(sorted_head);
zip_sort_renumber(order, args...);
}
} // namespace cs_helper
template <class T, class... Args>
std::vector<usize> zip_sort(std::vector<T>& head, Args&... args) {
usize n = head.size();
std::vector<std::pair<T, usize>> tmp(n);
for (usize i = 0; i < n; ++i) tmp[i] = std::make_pair(head[i], i);
std::sort(tmp.begin(), tmp.end());
std::vector<usize> order(n);
for (usize i = 0; i < n; ++i) order[i] = tmp[i].second;
cs_helper::zip_sort_renumber(order, head, args...);
return order;
}
#pragma endregion
void main_() {
usize N;
std::cin >> N;
std::vector<i32> A(N);
for (auto& el : A) std::cin >> el;
usize lst = 0;
u64 ans = 0;
for (usize i : range(0, N)) {
if (A[i] == 0) {
ans += (i - lst + 1) * (i - lst);
lst = i + 1;
}
}
ans += (N - lst + 1) * (N - lst);
std::cout << ((N * (N + 1) - ans) >> 1) << '\n';
// test
}
int main() { main_(); }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0