| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 938952 | riariti | Modsum (NOI12_modsum) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#line 1 "MODSUM.cpp"
#include <bits/stdc++.h>
#line 2 "/Users/jeff/Documents/git_repos/competitive/cplib/environment/dbg.hpp"
#if defined(local)
#include <debug>
#else
#define dbg(...)
#endif
#line 4 "MODSUM.cpp"
#line 9 "MODSUM.cpp"
#ifdef _MSC_VER
#include <intrin.h>
#endif
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n))
x *= 2;
return x;
}
#endif
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x)))
x++;
return x;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
#if __cplusplus >= 201703L
template <class S, auto op, auto e, class F, auto mapping, auto composition,
auto id>
struct lazy_segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
static_assert(
std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
"mapping must work as F(F, S)");
static_assert(
std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
"compostiion must work as F(F, F)");
static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
"id must work as F()");
#else
template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),
F (*composition)(F, F), F (*id)()>
struct lazy_segtree {
#endif
public:
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++)
d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--)
push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++)
update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--)
push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r)
return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l)
push(l >> i);
if (((r >> i) << i) != r)
push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1)
sml = op(sml, d[l++]);
if (r & 1)
smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--)
push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++)
update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r)
return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l)
push(l >> i);
if (((r >> i) << i) != r)
push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1)
all_apply(l++, f);
if (r & 1)
all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l)
update(l >> i);
if (((r >> i) << i) != r)
update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n)
return _n;
l += size;
for (int i = log; i >= 1; i--)
push(l >> i);
S sm = e();
do {
while (l % 2 == 0)
l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0)
return 0;
r += size;
for (int i = log; i >= 1; i--)
push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2))
r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size)
lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
} // namespace atcoder
using S = int;
S op(S a, S b) { return a + b; }
S e() { return 0; }
using F = int;
S mapping(F f, S x) { return f + x; }
F composition(F a, F b) { return a + b; }
F id() { return 0; }
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#define int std::int64_t
int n;
std::cin >> n;
std::vector<int> v(n), w(n);
for (int i = 0; i < 2 * n; i++) {
auto k = i / 2;
std::cin >> (i % 2 ? w[k] : v[k]);
}
dbg(n);
dbg(v);
dbg(w);
// a^4 + 2a^2 + 1
// let t = a^2 => (t + 1)^2
// (t * (t + 2)) % 5 + 1 also
// (a^2 + 1)^2
//
// 2 3
// 10 11 12
// 17
//
// 2 10 17 = 29
// 2 11 17 = 30
// 2 12 17 = 31
// 3 10 17 = 30
// 3 11 17 = 31
// 3 12 17 = 32
std::map<int, int> sum;
std::vector<int> pth;
auto rec = [&](auto &&self, int i, int s) {
if (i == n) {
sum[s]++;
dbg(pth, s);
return;
}
for (int j = v[i]; j <= w[i]; j++) {
pth.push_back(j);
self(self, i + 1, s + j);
pth.pop_back();
}
};
// rec(rec, 0, 0);
dbg(sum);
/*
4 1 5 2 3 4 6 1 5
17: [n = 4]
18: [v = {1,2,4,1}]
19: [w = {5,3,6,5}]
*/
// we are going to find the count of every sum basically
// after which we can trivially use above formula to find out
// the sum
//
// the length is the length of last block v[n - 1], w[n - 1]
//
// 1 = 1
// 1 1 = 2
// 1 1 = 2
// 1 = 1
// 1 1 1 1 1
// 2 2 2 2 2
// 2 2 2 2 1
// 1 1 1 1 1
// 1 3 5 6 6 5 3 1
//
// x5
// 1
// 2 1
// 2 2 1
// 1 2 2
// 1 2
// 1
// 1 1 1
// 1 1 1 1
// 1 1 1
// 1
//
// first step 4 to 6
// 1 1 1 1 1
// 1 1 1 1 1
// 1 1 1 1 1
// =
// 1 2 3 3 3 2 1
//
// second step 2 to 3
// 1 2 3 3 3 2 1
// 1 2 3 3 3 2 1
// =
// 1 3 5 6 6 5 3 1
//
// second step 1 to 5
// 1 3 5 6 6 5 3 1
// 1 3 5 6 6 5 3 1
// 1 3 5 6 6 5 3 1
// 1 3 5 6 6 5 3 1
// 1 3 5 6 6 5 3 1
// 1 4 9 15 21 25 21 15 9 4 1
//
// ofc the sum starts from the sum of v and ends at sum of w (which is the
// index of counter)
//
// 55: [sum =
// {(8,1),(9,4),(10,9),(11,15),(12,21),(13,25),(14,25),(15,21),(16,15),(17,9),(18,4),(19,1)}]
// this is correct
//
// at max 100 steps
//
// observe that the each value of the vector is controlling only some extra
// steps i.e
// in this case 5
// second step 1 to 5
// 1 3 5 6 6 5 3 1
// 1 3 5 6 6 5 3 1
// 1 3 5 6 6 5 3 1
// 1 3 5 6 6 5 3 1
// 1 3 5 6 6 5 3 1
// 1 1 1 1 1
// 3 3 3 3 3
// 5 5 5 5 5
// see the 1 idx 0 of the vector acts for len number of elements (0 to 4
// idxs) similarly for 3 idx 1 acts for len number of ele (1 to 5 idxs)
//
// use lazy segtree n times O(1000 ...) should be possible
std::ranges::reverse(v);
std::ranges::reverse(w);
auto l = w[0] - v[0] + 1;
std::vector<int> a(l, 1);
dbg(a);
atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(101 *
1001);
for (int i = 1; i < n; i++) {
l = w[i] - v[i] + 1;
dbg(l);
for (int j = 0; j < a.size(); j++) {
auto k = j + l - 1;
seg.apply(j, k + 1, a[j]);
}
a.resize(a.size() + l - 1);
for (int j = 0; j < a.size() + l; j++) {
a[j] = seg.get(j);
seg.set(j, 0);
}
}
dbg(a);
auto vs = std::accumulate(v.begin(), v.end(), 0);
auto ws = std::accumulate(w.begin(), w.end(), 0);
dbg(vs, ws, ws - vs + 1);
assert(a.size() == ws - vs + 1);
std::vector<std::pair<int, int>> vc;
for (int i = 0, v = vs; i < a.size(); i++, v++) {
vc.push_back({v, a[i]});
}
dbg(vc);
std::int64_t ans = 0;
for (auto [v, c] : vc) {
auto k = std::pow(v, 2);
std::int64_t res = static_cast<std::int64_t>(k) * (k + 2);
res %= 5;
res++;
dbg(res);
ans += res * c;
}
std::cout << ans << "\n";
#undef int
return 0;
}