| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 521887 |
2022-02-03T11:16:08 Z |
Cyanmond |
Pairs (IOI07_pairs) |
C++17 |
|
344 ms |
45520 KB |
#line 1 "paper.cpp"
#include <bits/stdc++.h>
#line 3 "library2/utility/int_alias.hpp"
using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#line 7 "library2/data-structure/segmenttree.hpp"
template <class M> class SegmentTree {
public:
using size_type = int;
using value_type = typename M::value_type;
private:
size_type m_n, m_size;
std::vector<value_type> m_nodes;
public:
explicit SegmentTree(const size_type n) : m_n(n), m_size(ceil_pow2(n)) {
m_nodes.assign(m_size << 1, M::identity());
}
SegmentTree(const size_type n, const value_type v) {
*this = SegmentTree(std::vector(n, v));
}
SegmentTree(const std::vector<value_type> &s) : m_n(s.size()), m_size(ceil_pow2(s.size())) {
m_nodes.assign(m_size << 1, M::identity());
std::copy(s.begin(), s.end(), m_nodes.begin() + m_size);
for (size_type i = m_size - 1; i != 0; --i)
internal_update(i);
}
void set(size_type i, const value_type &v) {
assert(i < m_n);
i += m_size;
m_nodes[i] = v;
for (i >>= 1; i != 0; i >>= 1)
internal_update(i);
}
value_type fold() const {
return m_nodes[1];
}
value_type fold(size_type l, size_type r) const {
assert(l <= r);
assert(r <= m_n);
value_type v_l = M::identity(), v_r = M::identity();
for (l += m_size, r += m_size; l < r; l >>= 1, r >>= 1) {
if (l & 1) v_l = M::operation(v_l, m_nodes[l++]);
if (r & 1) v_r = M::operation(m_nodes[--r], v_r);
}
return M::operation(v_l, v_r);
}
value_type get(const size_type i) const {
assert(i < m_n);
return m_nodes[m_size + i];
}
template <class F> size_type max_right(size_type l, const F &f) const {
assert(l <= m_n);
assert(f(M::identity()));
if (l == m_n) return m_n;
l += m_size;
value_type sum = M::identity();
do {
while (not(l & 1))
l >>= 1;
if (not f(M::operation(sum, m_nodes[l]))) {
while (l < m_size) {
l = l << 1;
if (f(M::operation(sum, m_nodes[l]))) sum = M::operation(sum, m_nodes[l++]);
}
return l - m_size;
}
sum = M::operation(sum, m_nodes[l++]);
} while ((l & (l - 1)) != 0);
return m_n;
}
template <class F> size_type min_left(size_type r, const F &f) const {
assert(r <= m_n);
assert(f(M::identity()));
if (r == 0) return 0;
r += m_size;
value_type sum = M::identity();
do {
--r;
while (r > 1 and (r & 1))
r >>= 1;
if (not f(M::operation(m_nodes[r], sum))) {
while (r < m_size) {
r = (r << 1) | 1;
if (f(M::operation(m_nodes[r], sum))) sum = M::operation(m_nodes[r--], sum);
}
return r + 1 - m_size;
}
sum = M::operation(m_nodes[r], sum);
} while ((r & (r - 1)) != 0);
return 0;
}
private:
static constexpr size_type ceil_pow2(const size_type n_) noexcept {
size_type res = 1;
while (res < n_)
res <<= 1;
return res;
}
void internal_update(const size_type i) {
m_nodes[i] = M::operation(m_nodes[i << 1], m_nodes[i << 1 | 1]);
}
};
#line 3 "library2/utility/int_literal.hpp"
constexpr i8 operator""_i8(unsigned long long n) noexcept {
return static_cast<i8>(n);
}
constexpr i16 operator""_i16(unsigned long long n) noexcept {
return static_cast<i16>(n);
}
constexpr i32 operator""_i32(unsigned long long n) noexcept {
return static_cast<i32>(n);
}
constexpr i64 operator""_i64(unsigned long long n) noexcept {
return static_cast<i64>(n);
}
constexpr u8 operator""_u8(unsigned long long n) noexcept {
return static_cast<u8>(n);
}
constexpr u16 operator""_u16(unsigned long long n) noexcept {
return static_cast<u16>(n);
}
constexpr u32 operator""_u32(unsigned long long n) noexcept {
return static_cast<u32>(n);
}
constexpr u64 operator""_u64(unsigned long long n) noexcept {
return static_cast<u64>(n);
}
#line 3 "library2/utility/rep.hpp"
class Range {
struct Iterator {
int itr;
constexpr Iterator(const int pos) noexcept : itr(pos) {}
constexpr void operator++() noexcept {
++itr;
}
constexpr bool operator!=(const Iterator &other) const noexcept {
return itr != other.itr;
}
constexpr int operator*() const noexcept {
return itr;
}
};
const Iterator first, last;
public:
explicit constexpr Range(const int f, const int l) noexcept
: first(f), last(std::max(f, l)) {}
constexpr Iterator begin() const noexcept {
return first;
}
constexpr Iterator end() const noexcept {
return last;
}
};
constexpr Range rep(const int l, const int r) noexcept {
return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
return Range(0, n);
}
#line 3 "library2/utility/scan.hpp"
template <typename T = int> T scan() {
T ret;
std::cin >> ret;
return ret;
}
#line 2 "library2/utility/setmin.hpp"
template <typename T> bool setmin(T& lhs, const T& rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
#line 5 "library2/utility/upb.hpp"
template <class Container, class T> constexpr int upb(const Container &c, const T &val) {
return static_cast<int>(std::distance(c.cbegin(), std::upper_bound(c.cbegin(), c.cend(), val)));
}
#line 10 "paper.cpp"
i64 solve_1() {
const int N = scan();
const i64 D = scan();
[[maybe_unused]] const i64 M = scan();
std::vector<i64> C(N);
for (auto &e : C) {
e = scan() - 1;
}
std::sort(C.begin(), C.end());
i64 answer = 0;
for (const int i : rep(N)) {
answer += upb(C, C[i] + D) - i - 1;
}
return answer;
}
void rotate45(int &a, int &b) {
int c = a - b, d = a + b;
a = c, b = d;
}
struct Monoid {
using value_type = int;
static int operation(int a, int b) {
return a + b;
}
static int identity() {
return 0;
}
};
i64 solve_2() {
const int N = scan();
const int D = scan();
const int M = scan();
std::vector<int> A(N), B(N);
for (const int i : rep(N)) {
A[i] = scan() - 1;
B[i] = scan() - 1;
rotate45(A[i], B[i]);
}
{
const int min =
std::min(*std::min_element(B.begin(), B.end()), *std::min_element(A.begin(), A.end()));
for (auto &e : A) {
e -= min;
}
for (auto &e : B) {
e -= min;
}
}
std::map<int, std::vector<int>> add_events;
std::map<int, std::vector<std::tuple<bool, int, int, int>>> sum_events;
std::vector<int> p;
p.reserve(3 * N);
for (const int i : rep(N)) {
p.push_back(A[i]);
p.push_back(A[i] - D);
p.push_back(A[i] + D + 1);
add_events[A[i]].push_back(B[i]);
sum_events[A[i] - D].push_back({false, i, B[i] - D, B[i] + D + 1});
sum_events[A[i] + D + 1].push_back({true, i, B[i] - D, B[i] + D + 1});
}
std::sort(p.begin(), p.end());
p.erase(std::unique(p.begin(), p.end()), p.end());
SegmentTree<Monoid> seg(5 * M);
std::vector<int> res(N);
for (const auto a : p) {
if (sum_events.find(a) != sum_events.end()) {
for (const auto &[type, idx, l, r] : sum_events[a]) {
const int sum = seg.fold(std::max(0, l), std::min(5 * M, r));
if (type) {
res[idx] += sum;
} else {
res[idx] -= sum;
}
}
}
if (add_events.find(a) != add_events.end()) {
for (const auto e : add_events[a]) {
seg.set(e, seg.get(e) + 1);
}
}
}
return (std::accumulate(res.begin(), res.end(), 0_i64) - N) / 2;
}
i64 solve_3() {
const int N = scan();
const int D = scan();
const int M = scan();
std::vector<int> A(N), B(N), C(N);
std::vector data(M, std::vector(5 * M + 1, std::vector(5 * M + 1, 0)));
for (const int i : rep(N)) {
A[i] = scan() - 1;
B[i] = scan() - 1;
C[i] = scan() - 1;
rotate45(B[i], C[i]);
}
{
const int min =
std::min(*std::min_element(B.begin(), B.end()), *std::min_element(C.begin(), C.end()));
for (auto &e : B) {
e -= min;
}
for (auto &e : C) {
e -= min;
}
}
for (const int i : rep(N)) {
++data[A[i]][B[i] + 1][C[i] + 1];
}
for (const int i : rep(M)) {
for (const int j : rep(5 * M + 1)) {
for (const int k : rep(5 * M)) {
data[i][j][k + 1] += data[i][j][k];
}
}
for (const int j : rep(5 * M)) {
for (const int k : rep(5 * M + 1)) {
data[i][j + 1][k] += data[i][j][k];
}
}
}
auto calc_sum = [&](const int h, const int r1, const int c1, const int r2, const int c2) {
return data[h][r2][c2] - data[h][r1][c2] - data[h][r2][c1] + data[h][r1][c1];
};
i64 answer = 0;
for (const int i : rep(N)) {
for (const int j : rep(M)) {
const int diff = std::abs(A[i] - j);
if (diff > D) {
continue;
} else {
int s = D - diff;
answer += calc_sum(j, std::max(0, B[i] - s), std::max(0, C[i] - s),
std::min(5 * M, B[i] + s + 1), std::min(5 * M, C[i] + s + 1));
}
}
}
return (answer - N) / 2;
}
int main() {
const int B = scan();
const i64 answer = (B == 1 ? solve_1() : (B == 2 ? solve_2() : solve_3()));
std::cout << answer << std::endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
292 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1440 KB |
Output is correct |
| 2 |
Correct |
26 ms |
1460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
1816 KB |
Output is correct |
| 2 |
Correct |
42 ms |
1860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
1828 KB |
Output is correct |
| 2 |
Correct |
43 ms |
1832 KB |
Output is correct |
| 3 |
Correct |
42 ms |
1840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4632 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
7824 KB |
Output is correct |
| 2 |
Correct |
71 ms |
8144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
103 ms |
9884 KB |
Output is correct |
| 3 |
Correct |
97 ms |
9284 KB |
Output is correct |
| 4 |
Correct |
102 ms |
9508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
344 ms |
27716 KB |
Output is correct |
| 2 |
Correct |
335 ms |
30248 KB |
Output is correct |
| 3 |
Correct |
128 ms |
14620 KB |
Output is correct |
| 4 |
Correct |
129 ms |
14408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
43468 KB |
Output is correct |
| 2 |
Correct |
33 ms |
43468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
2108 KB |
Output is correct |
| 2 |
Correct |
47 ms |
2216 KB |
Output is correct |
| 3 |
Correct |
43 ms |
2092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
24536 KB |
Output is correct |
| 2 |
Correct |
190 ms |
24508 KB |
Output is correct |
| 3 |
Correct |
156 ms |
24488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
45520 KB |
Output is correct |
| 2 |
Correct |
326 ms |
45480 KB |
Output is correct |
| 3 |
Correct |
280 ms |
45348 KB |
Output is correct |
