QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719739 | #9608. 皮鞋的多项式 | peaneval_kala | 100 ✓ | 1427ms | 113640kb | C++23 | 17.8kb | 2024-11-07 08:32:14 | 2024-11-07 08:32:14 |
Judging History
answer
#pragma GCC optimize(3, "unroll-loops", "no-stack-protector")
#define atsum(l, r) accumulate(l, r, 0)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
inline void chkmin(T &x, T y) { x = min(x, y); }
template <typename T>
inline void chkmax(T &x, T y) { x = max(x, y); }
namespace FastIO
{
// ------------------------------
#define IN_HAS_NEG
#define OUT_HAS_NEG
#define CHK_EOF
#define DISABLE_MMAP
// ------------------------------
#if __cplusplus < 201400
#error Please use C++14 or higher.
#endif
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if ( defined(LOCAL) || defined (_WIN32) ) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include<sys/mman.h>
#endif
#ifdef LOCAL
inline char gc() { return getchar(); }
inline void pc(char c) { putchar(c); }
#else
#ifdef DISABLE_MMAP
INLINE_V constexpr int _READ_SIZE = 1 << 18;
INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc()
{
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) )
{
_read_ptr = _read_buffer;
_read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin);
#ifdef CHK_EOF
if ( __builtin_expect(_read_ptr == _read_ptr_end, false) ) return EOF;
#endif
}
return *_read_ptr++;
}
#else
INLINE_V static const char *_read_ptr = (const char *)mmap(nullptr, INT_MAX, 1, 2, 0, 0);
inline char gc() { return *_read_ptr++; }
#endif
INLINE_V constexpr int _WRITE_SIZE = 1 << 18;
INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer;
inline void pc(char c)
{
*_write_ptr++ = c;
if ( __builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false) )
{
fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout);
_write_ptr = _write_buffer;
}
}
INLINE_V struct _auto_flush
{
~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); }
} _auto_flush;
#endif
#ifdef CHK_EOF
inline bool _isdigit(char c) { return ( c & 16 ) && c != EOF; }
inline bool _isgraph(char c) { return c > 32 && c != EOF; }
#else
inline bool _isdigit(char c) { return c & 16; }
inline bool _isgraph(char c) { return c > 32; }
#endif
template < class T >
INLINE_V constexpr bool _is_integer = numeric_limits < T >::is_integer;
template < class T >
INLINE_V constexpr bool _is_signed = numeric_limits < T >::is_signed;
template < class T >
INLINE_V constexpr bool _is_unsigned = _is_integer < T > && !_is_signed < T >;
template <> INLINE_V constexpr bool _is_integer < __int128 > = true;
template <> INLINE_V constexpr bool _is_integer < __uint128_t > = true;
template <> INLINE_V constexpr bool _is_signed < __int128 > = true;
template <> INLINE_V constexpr bool _is_unsigned < __uint128_t > = true;
#undef INLINE_V
inline void read(char &c) { do c = gc(); while ( !_isgraph(c) ); }
inline void read_cstr(char *s)
{
char c = gc(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) *s++ = c, c = gc();
*s = 0;
}
inline void read(string &s)
{
char c = gc(); s.clear(); while ( !_isgraph(c) ) c = gc();
while ( _isgraph(c) ) s.push_back(c), c = gc();
}
#ifdef IN_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void read(T &x)
{
char c = gc(); bool f = true; x = 0;
while ( !_isdigit(c) ) { if ( c == 45 ) f = false; c = gc(); }
if ( f ) while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
else while ( _isdigit(c) ) x = x * 10 - ( c & 15 ), c = gc();
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
inline void read(T &x)
{
char c = gc(); while ( !_isdigit(c) ) c = gc();
x = 0; while ( _isdigit(c) ) x = x * 10 + ( c & 15 ), c = gc();
}
inline void write(char c) { pc(c); }
inline void write_cstr(const char *s) { while ( *s ) pc(*s++); }
inline void write(const string &s) { for ( char c : s ) pc(c); }
#ifdef OUT_HAS_NEG
template < class T, enable_if_t < _is_signed < T >, int > = 0 >
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
if ( x >= 0 ) do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
else { pc(45); do buffer[digits++] = -( x % 10 ) | 48, x /= 10; while ( x ); }
while ( digits ) pc(buffer[--digits]);
}
template < class T, enable_if_t < _is_unsigned < T >, int > = 0 >
#else
template < class T, enable_if_t < _is_integer < T >, int > = 0 >
#endif
inline void write(T x)
{
char buffer[numeric_limits < T >::digits10 + 1]; int digits = 0;
do buffer[digits++] = ( x % 10 ) | 48, x /= 10; while ( x );
while ( digits ) pc(buffer[--digits]);
}
template < int N > struct _tuple_io_helper
{
template < class ...T >
static inline void _read(tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_read(x), read(get < N - 1 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x)
{ _tuple_io_helper < N - 1 >::_write(x), pc(32), write(get < N - 1 > (x)); }
};
template <> struct _tuple_io_helper < 1 >
{
template < class ...T >
static inline void _read(tuple < T... > &x) { read(get < 0 > (x)); }
template < class ...T >
static inline void _write(const tuple < T... > &x) { write(get < 0 > (x)); }
};
template < class ...T >
inline void read(tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_read(x); }
template < class ...T >
inline void write(const tuple < T... > &x) { _tuple_io_helper < sizeof...(T) >::_write(x); }
template < class T1, class T2 >
inline void read(pair < T1, T2 > &x) { read(x.first), read(x.second); }
template < class T1, class T2 >
inline void write(const pair < T1, T2 > &x) { write(x.first), pc(32), write(x.second); }
template < class T1, class ...T2 >
inline void read(T1 &x, T2 &...y) { read(x), read(y...); }
template < class ...T >
inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template < class T1, class ...T2 >
inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); }
template < class ...T >
inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template < class T >
inline void print(const T &x) { write(x); }
inline void print_cstr(const char *x) { write_cstr(x); }
template < class T1, class ...T2 >
inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template < class ...T >
inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); }
inline void println() { pc(10); }
inline void println_cstr() { pc(10); }
template < class ...T >
inline void println(const T &...x) { print(x...), pc(10); }
template < class ...T >
inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); }
}
using namespace FastIO;
template <typename T>
inline void clear(T &x) {
T y;
swap(x, y);
}
template <uint32_t mod = 998244353>
class Modint {
private:
static constexpr uint32_t get_r() {
uint32_t ret = mod;
for (int i = 0; i < 4; i++) ret *= 2 - mod * ret;
return ret;
}
static constexpr uint32_t r = get_r();
static constexpr uint32_t n2 = -uint64_t(mod) % mod;
static_assert(r * mod == 1 && mod < (1 << 30) && mod & 1);
uint32_t data;
public:
constexpr Modint() : data(0) {}
template <class int_t>
constexpr Modint(const int_t x)
: data(reduce(
uint64_t((sizeof(int_t) < sizeof(uint32_t) ? x : x % int_t(mod)) +
mod) *
n2)){};
static constexpr uint32_t reduce(const uint64_t x) {
return (x + uint64_t(uint32_t(x) * (-r)) * mod) >> 32;
}
constexpr Modint &operator+=(const Modint &r) {
if (int32_t(data += r.data - 2 * mod) < 0) {
data += 2 * mod;
}
return *this;
}
constexpr Modint &operator-=(const Modint &r) {
if (int32_t(data -= r.data) < 0) {
data += 2 * mod;
}
return *this;
}
constexpr Modint &operator*=(const Modint &r) {
return data = reduce((uint64_t)data * r.data), *this;
}
constexpr Modint &operator/=(const Modint &r) { return *this *= r.inv(); }
constexpr friend Modint operator+(Modint l, const Modint &r) {
return l += r;
}
constexpr friend Modint operator-(Modint l, const Modint &r) {
return l -= r;
}
constexpr friend Modint operator*(Modint l, const Modint &r) {
return l *= r;
}
constexpr friend Modint operator/(Modint l, const Modint &r) {
return l /= r;
}
constexpr friend bool operator==(Modint l, const Modint &r) {
return l.value() == r.value();
}
constexpr Modint operator-() const { return Modint() - Modint(*this); }
template <class int_t>
constexpr Modint pow(int_t r) const {
Modint res(1), w(*this);
for (; r; r >>= 1, w *= w)
if (r & 1) res *= w;
return res;
}
constexpr Modint inv() const { return pow(mod - 2); }
constexpr uint32_t value() const {
uint32_t res = reduce(data);
return res >= mod ? res - mod : res;
}
};
using modint = Modint<>;
vector<modint> wn[22], iwn[22];
const modint inv2 = modint(2).inv();
struct Poly {
vector<modint> vec;
inline modint operator[](int x) const {
return 0 <= x && x < vec.size() ? vec[x] : 0;
}
inline Poly() {}
inline Poly(const vector<modint> &x) : vec(x) {}
inline Poly(const initializer_list<modint> &x) : vec(x) {}
inline bool empty() const { return vec.empty(); }
inline int size() const { return (int)vec.size(); }
inline void resize(int x) { vec.resize(x); }
inline auto begin() { return vec.begin(); }
inline auto end() { return vec.end(); }
inline auto begin() const { return vec.begin(); }
inline auto end() const { return vec.end(); }
inline bool empty() { return vec.empty(); }
inline modint &operator[](int x) { return vec[x]; }
inline Poly divxk(int x) const {
return Poly(vector<modint>(vec.begin() + min(x, size()), vec.end()));
}
inline Poly modxk(int x) const {
return Poly(vector<modint>(vec.begin(), vec.begin() + min(x, size())));
}
inline int size() { return vec.size(); }
inline static void NTT(Poly &c, int len, int type) {
if (len == 0) return;
vector<int> rev;
rev.resize(1 << len);
for (int i = 0; i < (1 << len); i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << len - 1);
for (int i = 0; i < (1 << len); i++) {
if (rev[i] < i) swap(c[i], c[rev[i]]);
}
for (int i = 0; i < len; i++) {
if (!wn[i].size()) {
modint k = modint(3).pow((998244353 - 1) / (2 << i));
wn[i].resize(1 << i);
wn[i][0] = 1;
for (int j = 1; j < (1 << i); j++) wn[i][j] = wn[i][j - 1] * k;
}
if (!iwn[i].size()) {
modint k = modint(3).pow((998244353 - 1) / (2 << i));
k = k.inv();
iwn[i].resize(1 << i);
iwn[i][0] = 1;
for (int j = 1; j < (1 << i); j++)
iwn[i][j] = iwn[i][j - 1] * k;
}
if (type == 1)
for (int j = 0; j < (1 << len); j += 2 << i) {
#pragma GCC unroll 8
for (int k = 0; k < (1 << i); k++) {
modint a = c[j + k], b = c[j + (1 << i) + k] * wn[i][k];
c[j + k] = (a + b);
c[j + (1 << i) + k] = (a - b);
}
}
else
for (int j = 0; j < (1 << len); j += 2 << i) {
#pragma GCC unroll 8
for (int k = 0; k < (1 << i); k++) {
modint a = c[j + k],
b = c[j + (1 << i) + k] * iwn[i][k];
c[j + k] = (a + b);
c[j + (1 << i) + k] = (a - b);
}
}
}
if (type == -1) {
modint inv = inv2.pow(len);
for (int j = 0; j < (1 << len); j++) c[j] *= inv;
}
}
inline friend Poly operator*(Poly a, Poly b) {
if (!a.size() || !b.size()) return Poly{};
if (a.size() + b.size() <= 30) {
Poly ans;
ans.resize(a.size() + b.size() - 1);
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++) ans[i + j] += a[i] * b[j];
return ans;
}
int len = a.size() + b.size() - 1;
int qwq = 0;
while ((1 << qwq) < len) qwq++;
a.resize(1 << qwq), b.resize(1 << qwq);
NTT(a, qwq, 1), NTT(b, qwq, 1);
for (int i = 0; i < (1 << qwq); i++) a[i] *= b[i];
NTT(a, qwq, -1);
return a.modxk(len);
}
inline friend Poly operator*(Poly a, modint c) {
for (auto &v : a.vec) v *= c;
return a;
}
inline Poly operator*=(const Poly & b) { return *this = *this * b; }
inline friend Poly operator-(const Poly &a, const Poly &b) {
vector<modint> c(max(a.size(), b.size()));
for (int i = 0; i < c.size(); i++) c[i] = a[i] - b[i];
return c;
}
inline friend Poly operator+(const Poly &a, const Poly &b) {
vector<modint> c(max(a.size(), b.size()));
for (int i = 0; i < c.size(); i++) c[i] = a[i] + b[i];
return c;
}
inline Poly operator-=(const Poly &b) { return *this = *this - b; }
inline Poly operator+=(const Poly &b) { return *this = *this + b; }
inline Poly operator*=(modint b) { return *this = *this * b; }
inline Poly derivative() const {
if (vec.empty()) return Poly();
vector<modint> z(size() - 1);
for(int i = 1; i < size(); i++) z[i - 1] = vec[i] * i;
return z;
}
inline Poly integrate() const {
vector<modint> z(size() + 1);
for (int i = 1; i <= size(); i++) z[i] = vec[i - 1] / i;
return z;
}
inline Poly inv(int x) const {
Poly z({vec[0].inv()});
int n = 1;
while (n < x) n <<= 1, z = (z * (Poly({2}) - modxk(n) * z)).modxk(n);
return z.modxk(x);
}
inline Poly ln(int x) const {
assert(vec[0] == 1);
return (derivative() * inv(x)).integrate().modxk(x);
}
inline Poly exp(int x) const {
assert(vec[0] == modint(0));
Poly z({1});
int n = 1;
while (n < x)
n <<= 1, z = (z * (Poly({1}) - z.ln(n) + modxk(n))).modxk(n);
return z.modxk(x);
}
inline Poly sqrt(int x) const {
assert(vec[0] == modint(1));
Poly z({1});
int n = 1;
modint inv2 = modint(2).inv();
while (n < x) n <<= 1, z = (z + (modxk(n) * z.inv(n)).modxk(n)) * inv2;
return z.modxk(x);
}
inline void println() {
for (auto c : vec) write(c.value(), ' ');
FastIO::println();
}
};
const int N = 1e5 + 10;
int n, q, B, fa[N];
basic_string<int> vec[N];
Poly c[N], f[N], big[N];
int cc, id[N];
inline Poly mul3(Poly a, Poly b, Poly c) {
if (b.size() > c.size()) swap(b, c);
return (a * b) * c;
}
inline void merge(int x, int y) {
f[x] *= f[y];
if (f[x].size() > B && (id[x] && id[y])) {
++cc;
big[cc] = mul3(f[x], big[id[x]], big[id[y]]);
f[x] = {1};
id[x] = cc;
} else if (f[x].size() > B) ++cc, big[cc] = f[x] * big[id[x] | id[y]], f[x] = {1}, id[x] = cc;
else if (id[x] && id[y]) ++cc, big[cc] = big[id[x]] * big[id[y]], id[x] = cc;
else id[x] |= id[y];
}
void dfs(int u) {
f[u] = c[u];
if (f[u].size() > B)
++cc, big[cc] = f[u], id[u] = cc, f[u] = {1};
for (int v : vec[u]) if (v != fa[u]) fa[v] = u, dfs(v), merge(u, v);
}
inline modint query(int u, int x) {
if (x < 0) return modint();
modint ans;
if (!id[u]) {
for (int i = 0; i < min(x + 1, int(f[u].size())); i++) ans += f[u][i];
return ans;
}
for (int i = 0; i < min(x + 1, int(f[u].size())); i++) ans += f[u][i] * big[id[u]][min(big[id[u]].size() - 1, x - i)];
return ans;
}
int main() {
read(n, q), B = max(1.0, sqrt(n * log2(n)));
big[0] = {1};
for (int i = 1; i <= n; i++) {
int k;
read(k);
c[i].resize(k + 1);
for (int j = 0, x; j <= k; j++) read(x), c[i][j] = x;
}
for (int i = 1; i < n; i++) {
int u, v;
read(u, v), vec[u] += v, vec[v] += u;
}
dfs(1);
big[++cc] = f[1] * big[id[1]], f[1] = {1}, id[1] = cc;
// cerr << "find id:" << id[1] << endl;
for (int i = 1; i <= cc; i++)
for (int j = 1; j < big[i].size(); j++) big[i][j] += big[i][j - 1];
int last = 0;
while (q--) {
int x, l, r;
read(x, l, r);
x ^= last, l ^= last, r ^= last;
println(last = (query(x, r) - query(x, l - 1)).value());
}
return 0;
}
詳細信息
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 16ms
memory: 15236kb
input:
1977 200000 0 883734638 1 497045124 50605999 0 467033353 8 514303373 873913661 21585656 827572829 831599042 669912647 980444584 921677622 90967524 0 111009203 0 980468811 1 965285721 647475291 0 55665482 0 810210109 5 99482052 915734955 536563337 860629716 489661090 127640528 4 452261176 414532348 8...
output:
0 0 0 1462214 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 709010908 0 0 0 0 0 0 0 0 0 0 0 0 0 0 362560754 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 887205253 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 532388854 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 200000 numbers
Test #2:
score: 7
Accepted
time: 17ms
memory: 15080kb
input:
1969 200000 1 928278040 49291189 0 106316044 7 355985609 701602147 528629206 472008316 626845782 871506163 793475066 634852555 0 193911795 1 498772599 387035156 2 244940676 15788848 225049996 8 257966353 171785747 687353797 643745787 25069581 248781417 212047281 295151595 525248876 2 606862291 21936...
output:
0 0 702752596 0 0 0 564436252 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 539882987 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 421207407 0 0 0 0 0 ...
result:
ok 200000 numbers
Test #3:
score: 7
Accepted
time: 12ms
memory: 14684kb
input:
2000 200000 0 230695610 4 400302240 129755410 740309716 633048240 594259574 2 261261651 610028309 279096898 0 306295327 1 411519353 880936332 4 458323735 111990362 693959473 50334178 49499787 0 451592459 1 114402580 931927324 4 639243873 254122580 669324541 571247271 275880979 0 440954066 1 43964805...
output:
0 0 801713754 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 807839363 0 845789441 0 0 0 0 0 0 0 0 180971215 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 791867965 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 514100741 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 995968989 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8782...
result:
ok 200000 numbers
Test #4:
score: 7
Accepted
time: 27ms
memory: 15204kb
input:
1978 200000 1 191987956 540466676 1 120742551 206257774 2 744430486 875250521 181042024 0 103091601 0 304724279 0 649017453 0 145685556 0 599144446 0 364188280 0 57833875 3 414338956 791946816 770890256 830048461 0 819249191 0 755199883 1 758814940 693449562 1 280052104 142092003 0 214207528 0 85521...
output:
0 0 0 0 0 0 0 0 0 0 0 0 574798441 0 0 551851346 0 0 0 0 0 0 298923018 0 0 0 0 0 706319639 0 0 932127532 0 0 0 0 506810290 0 0 375480684 0 0 0 0 0 575707276 0 769974190 0 0 0 0 0 0 0 0 0 255132253 234643792 0 436442475 0 0 0 0 0 0 770777820 0 0 0 0 382421721 0 0 10702740 0 0 912641116 0 679541132 0 0...
result:
ok 200000 numbers
Test #5:
score: 7
Accepted
time: 11ms
memory: 14716kb
input:
1997 200000 1 609381747 833571580 1 102342468 526127035 1 880931004 909374728 2 103826707 729151512 34293902 1 273372046 293953096 0 554926428 0 676458000 1 401799287 357803550 1 695810053 794616522 0 748711966 1 967175820 34877055 2 257806263 264285746 818013686 1 576641758 75701100 0 795476926 0 7...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 996352329 0 0 0 0 61024835 0 0 424430639 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 392760029 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 442026045...
result:
ok 200000 numbers
Subtask #2:
score: 3
Accepted
Test #6:
score: 3
Accepted
time: 37ms
memory: 22156kb
input:
98154 200000 0 948053956 0 149079029 0 871940052 0 888807640 0 284687863 0 760258916 0 916765457 0 121680504 0 210430381 0 162441114 0 640680402 0 269559148 0 706423649 0 619089994 0 776236890 0 44769489 0 863235377 0 283984837 0 251593760 0 863377054 0 40488948 0 100272768 0 628132233 0 18841959 0 ...
output:
0 160622568 939846745 221659137 0 312930382 620657950 975124531 0 241389446 233242086 656904774 0 666641212 127400637 0 0 61866892 388266897 17714856 158666308 181172732 0 231863345 0 0 993493871 0 945624744 0 53582097 0 553931157 940627115 0 864491900 0 0 910285591 0 0 0 0 810021023 0 957355731 870...
result:
ok 200000 numbers
Test #7:
score: 3
Accepted
time: 39ms
memory: 22096kb
input:
98566 200000 0 209181684 0 889317979 0 925862494 0 861680823 0 629292192 0 781545895 0 58892045 0 300501945 0 510137985 0 764792857 0 551445762 0 771899874 0 828696971 0 260462870 0 535761660 0 532161459 0 187099 0 691412616 0 891055462 0 283180276 0 446617517 0 928434806 0 974119517 0 895921491 0 8...
output:
0 541915644 0 0 0 344789573 37160095 0 0 378148422 0 27407348 0 510146116 0 0 593724632 308323897 0 208041958 834526238 308130263 413718362 0 0 452600858 215844992 0 0 138748183 0 597752749 0 0 0 131857104 0 0 583969453 644145934 277456647 0 730806159 210434799 329144450 0 271266199 0 0 532721033 33...
result:
ok 200000 numbers
Subtask #3:
score: 20
Accepted
Test #8:
score: 20
Accepted
time: 991ms
memory: 84796kb
input:
97330 200000 2 356080749 854511831 888131963 0 533633039 0 260190631 0 217335008 2 998111375 903316988 891866314 0 507509609 0 556810297 1 190927168 988903728 1 270553180 387224380 0 360295480 0 775464651 0 755424805 0 71030175 0 690904984 0 702271750 0 360541906 0 903384679 0 769283169 0 6990072 0 ...
output:
977291091 128984561 364900240 670134422 109312967 116219802 633246879 791832029 188822171 313954797 872698950 326842267 58045309 613915890 34453063 626081681 891712143 675586354 509834775 529836633 409512272 657071096 11862851 695651906 98170281 194125828 955037714 807908792 212191825 825295990 2244...
result:
ok 200000 numbers
Test #9:
score: 20
Accepted
time: 582ms
memory: 55600kb
input:
96880 200000 0 155849542 1 895865131 748889613 0 28666287 0 959676113 0 436568647 0 514279644 1 636928010 199253041 1 806543723 563843226 0 296862731 1 617330202 619480133 0 832224863 1 207080707 411689441 1 550833908 670195492 0 980814251 0 685006368 0 558249647 0 20614515 1 412246213 873717215 0 9...
output:
440357773 924848770 340312385 268399218 703705351 283032621 527143532 527723719 936920505 815914636 237227259 965189344 992799087 987559316 196769340 130556674 652234120 950203104 295087063 429164775 959998385 480555801 559603216 617304409 636888726 251764185 734722233 932706757 260865681 154570949 ...
result:
ok 200000 numbers
Test #10:
score: 20
Accepted
time: 584ms
memory: 57080kb
input:
99119 200000 1 193445750 73279632 0 159943777 0 741212402 0 433101693 0 492169150 0 295804258 1 875516477 748591364 1 847628456 521055346 0 720470433 0 550284345 0 645519907 0 749938197 0 728894207 0 14951672 0 929957765 0 738265973 0 856320168 1 663420785 638700238 0 779605078 1 862023258 913300109...
output:
107826286 763543631 427034420 121557813 640560432 778202723 103828218 293968965 588012467 317760045 345087369 219212550 836926992 376387667 550043054 728607728 282292412 228698918 347936331 249473140 667006058 385530595 234024405 524452029 871686154 73351486 115718734 415219796 6724454 728022916 226...
result:
ok 200000 numbers
Test #11:
score: 20
Accepted
time: 1025ms
memory: 85548kb
input:
91157 200000 0 391787528 0 128755192 3 417616809 157059090 109145241 105518767 4 168117201 184583673 611518413 449165163 785494567 0 335176806 0 767105706 6 197456690 26613590 508404062 688256680 114381875 509628059 822034065 1 134962121 111013253 0 273868329 0 995896690 0 727430687 4 52157529 93530...
output:
487041619 893275322 142402824 686731750 294920099 62183929 203079049 439067611 576528554 1804420 325046088 569012939 705848070 441856702 186405396 545740489 381312300 369454907 220000496 165233678 885597752 351769009 923484288 312188024 490873204 137214518 826339916 76816562 934429093 978384021 5417...
result:
ok 200000 numbers
Test #12:
score: 20
Accepted
time: 580ms
memory: 59060kb
input:
99054 200000 5 254591921 45593960 652041376 677254663 473209153 872993623 2 971834440 872618713 873774372 2 972786941 469418722 54936289 0 81056452 2 19714994 377576837 670989944 0 576526565 1 386619382 254596911 0 556584884 0 660262022 2 695328773 305942756 847812140 3 481581243 889943689 200600389...
output:
71125289 915873767 805882401 172961705 778575612 745456836 142968723 651540653 62367309 595540188 481360743 493180227 29659645 130302698 499160808 175915570 885742426 369665055 759536493 373302350 748795932 868454695 156649635 515858502 343254972 915736493 855732654 833555582 267541889 927511069 635...
result:
ok 200000 numbers
Subtask #4:
score: 20
Accepted
Test #13:
score: 20
Accepted
time: 211ms
memory: 31868kb
input:
50000 50000 1 610345459 691411093 1 476654936 529767753 1 8856530 640833948 1 961473497 456987897 1 462733802 114971681 1 662244461 415955667 1 717992437 907944693 1 346097988 176526535 1 805826501 182409272 1 33105050 971783530 1 45972429 258997374 1 964103067 796756441 1 958668755 735146502 1 9543...
output:
0 0 0 0 0 0 0 610268301 297428232 729194415 0 0 506964543 0 198345028 778136423 0 89695571 651093422 174709 799469987 0 0 0 0 374762615 64155221 0 644085102 355318236 625240586 0 0 0 0 611217681 0 246858712 0 946363040 766457000 0 0 0 0 0 0 0 885388926 324657374 0 0 608041499 0 0 0 595311003 0 0 790...
result:
ok 50000 numbers
Test #14:
score: 20
Accepted
time: 440ms
memory: 46964kb
input:
50000 50000 1 284188823 730123812 1 578529655 782975708 1 682107201 169640319 1 504919829 297067490 1 126340369 681480864 1 702290552 331608873 1 89823300 900339069 1 661791786 696739097 1 146107507 457302386 1 309885170 133384173 1 1601509 445278250 1 82308245 611577805 1 575317 145972663 1 3340187...
output:
118484783 20950737 827095992 192485904 949696395 760932709 0 827083836 737333618 0 0 936633428 869751868 21893026 0 0 700825516 0 0 140717292 495143473 757971245 71851829 758042728 168032853 336898224 82834617 0 50295595 473191194 0 603695852 88648030 191908163 0 0 347045240 304736441 10279888 28050...
result:
ok 50000 numbers
Test #15:
score: 20
Accepted
time: 214ms
memory: 31332kb
input:
50000 50000 1 908905842 879908939 1 69131120 893333490 1 766104239 502577285 1 598541702 20672714 1 19129534 562935613 1 17855501 931751363 1 817552765 924309216 1 601703730 928273412 1 280909912 198946276 1 259187488 350711225 1 460175073 829804287 1 142301100 182462131 1 440043596 503299121 1 4954...
output:
608336339 0 479640409 0 0 0 304101361 575455842 631421870 0 921143438 0 0 614891272 920725723 987924343 0 0 944939021 0 842440434 0 0 219630310 595973439 303974010 0 0 0 0 266178665 352670733 355014561 0 0 0 15870579 900144368 490797433 594447900 0 521603348 0 0 763764981 0 0 238461206 0 0 22187316 ...
result:
ok 50000 numbers
Test #16:
score: 20
Accepted
time: 218ms
memory: 32416kb
input:
50000 50000 1 132666924 481468407 1 233104347 925423798 1 196520221 188340478 1 880316330 347865528 1 362038740 586184357 1 260977445 869456691 1 413836428 997205621 1 925267833 389145261 1 412474208 605923400 1 275275170 580329557 1 248067291 201190325 1 267032222 546518461 1 60371460 731907388 1 2...
output:
284858974 0 521392986 0 0 419555545 0 279474735 869174793 0 0 0 0 327341031 0 887506929 253382960 0 549720153 0 470223182 448985266 0 0 0 571599922 0 0 0 0 687095778 0 0 523720173 340816378 0 927700876 0 0 0 117671213 493623216 0 269849900 992438456 0 233002506 0 875191758 582797638 0 0 222273961 0 ...
result:
ok 50000 numbers
Test #17:
score: 20
Accepted
time: 234ms
memory: 32480kb
input:
50000 50000 1 570249482 963041872 1 164483403 404765803 1 181145508 416450528 1 536381689 716629517 1 19355006 80481263 1 627992141 65443806 1 185587289 129800096 1 667577148 11179897 1 512133278 870239643 1 135475895 124891452 1 917154463 721424462 1 243207295 964207791 1 348452088 67572040 1 16668...
output:
76593910 267735832 0 0 379967837 128237686 782639460 0 0 155844091 934345203 666090547 241913187 0 0 884593508 0 199971361 0 876108660 362635493 0 0 0 0 93781856 635645613 903201788 0 794166948 108363160 0 0 937730015 0 641371731 0 836048882 0 584024075 0 0 0 0 169018859 0 0 0 0 984231395 0 0 102506...
result:
ok 50000 numbers
Test #18:
score: 20
Accepted
time: 303ms
memory: 37252kb
input:
50000 50000 1 374439028 76801984 1 198570918 279646664 1 738529796 230017198 1 93739509 610640325 1 525884738 858818589 1 949692556 761814293 1 235726510 7565628 1 45230953 841809717 1 624654181 697155421 1 56572048 898846486 1 181498104 803293558 1 123843798 593520342 1 590491409 791005242 1 888374...
output:
864276436 440159890 536780052 321076766 468541452 986423750 663920928 988866764 260419539 0 0 0 0 917177790 340374136 783267120 861409101 702416442 365736645 250814244 0 889464570 0 158883242 778105434 403578126 718091928 0 110804297 685559904 0 17649876 0 811219235 0 320574087 469972593 932031629 3...
result:
ok 50000 numbers
Test #19:
score: 20
Accepted
time: 217ms
memory: 31504kb
input:
50000 50000 1 33459023 378743148 1 649009512 322497285 1 4159024 354205478 1 635048826 663468389 1 822658913 27307310 1 195454131 803172665 1 875401287 11624886 1 289967362 733461614 1 251177354 546439677 1 600412174 876096433 1 230834162 878747260 1 269956920 918423510 1 254773805 746291985 1 29210...
output:
144329675 0 937010808 0 387987066 256520687 0 415222201 574050902 0 0 78330661 774146527 545659020 0 0 676856924 0 0 0 371281553 0 724389591 180883171 60120880 758706582 260395535 86733354 0 0 454943744 866940819 213813873 343349330 781027374 265021034 322573212 71290236 0 0 333346154 117482220 1005...
result:
ok 50000 numbers
Test #20:
score: 20
Accepted
time: 1076ms
memory: 113640kb
input:
50000 50000 1 740199008 613475557 1 922880359 842126974 1 451019859 922790230 1 178429894 72393602 1 569458862 898768795 1 834271550 7640899 1 645877613 459724785 1 15126535 700620044 1 546332191 981494527 1 693370057 48191032 1 599613461 710991225 1 560674975 816111048 1 324902849 638444457 1 41924...
output:
874743447 472418696 893475459 768083962 844890219 0 491167288 0 662057644 33125578 0 0 0 380253379 790862397 453081406 0 0 64445999 613775426 0 0 0 669660760 597392638 0 37758869 0 11684083 11431232 0 827641705 191050687 39123082 0 821861901 0 658965581 0 107926632 720677708 0 0 240074723 949362284 ...
result:
ok 50000 numbers
Subtask #5:
score: 20
Accepted
Test #21:
score: 20
Accepted
time: 70ms
memory: 19968kb
input:
19854 20000 1 150513542 240180212 0 987796281 0 90054116 1 191708494 438440429 0 192815969 0 867402303 1 531762469 210966860 2 95662022 345368425 199338548 0 269135053 0 816253511 0 66854944 0 319745952 0 202288549 0 492853777 0 410846691 0 824737426 0 821545014 0 72050044 0 534080091 1 542636124 52...
output:
913323334 0 0 0 0 0 0 0 0 0 0 0 901017606 0 0 0 0 0 954099396 0 0 432419999 0 0 0 0 0 0 0 761082946 259729654 0 0 0 0 790235355 933098570 356668385 125624181 0 0 0 0 917034405 0 321407524 0 671256345 39032345 0 0 676929142 0 0 0 0 0 0 0 0 910494481 0 0 0 733125978 0 0 835461650 0 154343024 690428959...
result:
ok 20000 numbers
Test #22:
score: 20
Accepted
time: 61ms
memory: 19732kb
input:
19416 20000 1 813812350 62928444 2 446931520 455152410 865811291 1 483245225 719509880 0 10630578 1 722267364 499990463 0 978295677 0 524126644 2 398577038 701788899 939255653 0 945953310 0 358029034 1 54632159 541649711 0 714215963 0 760637762 1 792667329 540131052 1 336329275 197811762 0 594815129...
output:
0 0 0 0 0 0 0 0 691960524 0 0 0 0 0 0 0 0 0 0 917519575 0 0 0 0 457906160 686627668 0 263875204 0 0 0 860458574 0 0 197732443 0 0 0 0 0 0 0 0 0 0 0 0 0 619069496 0 0 145464796 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 409777622 309523189 862407937 0 0 954411456 0 0 0 0 0 0 304719397 0 548777971 176155...
result:
ok 20000 numbers
Test #23:
score: 20
Accepted
time: 63ms
memory: 20304kb
input:
19645 20000 1 738216072 655062389 0 478261419 28 38522218 205802590 608351714 423733656 368037127 943951223 529243126 691493532 378826276 32699256 849862664 799709335 113704178 671006657 736000878 683394539 338518052 850384023 536423162 225738416 276528868 965415989 455460104 274736758 547583027 423...
output:
0 710035374 349663621 61124181 0 0 0 0 0 0 0 0 0 0 0 0 0 0 694466943 0 0 0 0 103025366 0 0 108158012 0 0 898653012 0 0 0 0 124734988 0 628306562 0 0 0 0 0 829055370 0 942321667 0 0 0 0 100614270 0 666765805 277413825 0 0 0 0 492192785 0 0 0 0 517011159 0 0 0 0 172598073 0 258513717 233404540 8590182...
result:
ok 20000 numbers
Test #24:
score: 20
Accepted
time: 71ms
memory: 20048kb
input:
19847 20000 4 815026590 930615671 256423615 192058090 553677398 0 854407447 3 121205405 14847480 141687199 287623506 2 379798536 291209656 593839232 1 352031200 841240984 0 295186159 0 841042115 0 679392127 0 420742492 2 891756622 260075296 417909411 0 645458804 0 681889229 0 29119165 0 99142741 3 7...
output:
470171472 213398321 0 0 55462715 0 338144412 0 0 0 0 0 0 0 698725184 0 0 0 0 47366191 0 317326831 0 0 0 239746199 214366720 0 0 0 0 0 279091720 0 86836316 0 0 0 35432299 0 308555884 0 319326811 0 0 0 305535605 0 358646410 0 0 131375996 0 0 0 0 0 0 0 0 570823027 0 0 80022023 0 954809219 0 0 0 0 26917...
result:
ok 20000 numbers
Test #25:
score: 20
Accepted
time: 68ms
memory: 19620kb
input:
19990 20000 3 575964327 889968526 762346953 464212918 0 91433877 0 762285092 1 703259059 61874142 2 130773960 696187633 280576635 1 163442506 294293968 0 134582456 0 525908094 2 981613234 494831823 871173319 0 320232487 0 951459253 0 725136632 2 48590419 631199232 992008959 1 860836891 867326137 1 6...
output:
90336621 0 741001438 326700634 0 0 0 0 0 0 925215064 0 0 863889195 0 0 0 0 0 576304546 0 0 0 0 583889751 0 0 0 0 0 0 813389361 0 0 0 0 0 0 0 108311310 0 0 653689603 0 0 0 91295650 0 347062400 0 0 0 0 620038417 846141331 99345412 0 581988923 0 0 0 0 365053652 29464872 917029396 788177507 288943414 0 ...
result:
ok 20000 numbers
Test #26:
score: 20
Accepted
time: 63ms
memory: 19664kb
input:
19302 20000 1 140879209 815790450 0 263312184 2 357492390 407721624 927753023 17 329030216 687250506 904721674 66559073 150996400 582272412 140464848 806623151 989399143 916248414 596527559 964780629 802988469 182625819 764316767 594475067 203564894 275476377 0 547777698 0 34169169 0 93303556 0 5807...
output:
0 0 132910965 0 127962650 0 453633700 0 0 451482843 0 0 0 388743057 0 0 293560154 874329518 0 0 0 0 0 0 0 0 0 0 766081674 0 0 234642116 0 0 669563153 0 748448386 0 0 0 0 0 0 0 0 0 670410122 87350607 0 416323263 174794844 0 0 0 0 0 0 196859095 0 0 0 0 644332981 0 0 0 0 0 0 0 0 0 469599960 0 0 0 0 931...
result:
ok 20000 numbers
Test #27:
score: 20
Accepted
time: 61ms
memory: 20128kb
input:
19653 20000 1 906614788 500628713 0 988012762 0 284902421 0 704468047 0 872560811 1 907887753 600402772 0 767950811 0 118754288 0 290736011 0 217729487 1 190172852 683598286 0 723859834 0 220112811 0 448174595 0 39653265 0 770732977 0 458450918 0 438730398 0 183195813 0 191514564 0 2928127 0 3007322...
output:
0 244727120 0 0 132988676 354295625 0 667761790 0 0 0 0 0 822615931 0 0 0 0 0 0 504618092 0 973780962 0 0 0 0 737475269 0 0 0 383245743 0 0 10261578 551768502 0 835642191 0 0 69015099 0 0 773914454 0 0 0 0 0 193232063 0 0 0 0 0 230203189 0 0 0 0 0 0 0 0 120778708 0 949822563 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 20000 numbers
Test #28:
score: 20
Accepted
time: 70ms
memory: 19660kb
input:
19072 20000 0 910136763 1 809343877 577693489 0 805540439 0 728993500 0 234081004 1 891104112 210354669 0 262384318 0 568913493 0 376708574 1 145377149 421745582 0 108964429 0 697119989 0 615671424 0 697025092 0 222804661 0 927317484 1 66775292 771115618 0 405877157 1 977355316 502648356 1 218406564...
output:
0 0 0 558272462 0 0 0 0 0 0 0 328733917 446478844 0 0 0 0 0 0 848724549 0 0 980511070 0 0 597411269 0 127279175 0 0 0 0 0 739852501 0 0 0 0 0 0 568449517 589452941 0 0 0 0 791777304 0 0 0 0 114744131 322763812 613885875 52417149 0 0 0 0 149449664 0 0 644257795 0 725958460 276312482 499158209 8075964...
result:
ok 20000 numbers
Test #29:
score: 20
Accepted
time: 12ms
memory: 17656kb
input:
20000 20000 0 614936162 0 182986322 0 40697275 0 824161988 0 240412566 0 287310162 0 63000758 0 958628891 0 139827408 0 971860786 0 325782161 0 726800064 0 392930207 0 911604309 0 904980384 0 508941069 0 641836609 0 759719860 0 732767740 0 94630498 0 390558752 0 764408563 0 40013248 0 414628626 0 87...
output:
664811563 788614780 974744409 578158051 972633254 83874056 204528292 473798071 213046046 429307018 595958938 227031150 671368761 461998185 115917717 744731293 465171055 551785804 318236143 171800659 801541585 707676156 58721393 116249265 334321741 90511883 550891644 284752711 828872978 231691412 450...
result:
ok 20000 numbers
Test #30:
score: 20
Accepted
time: 52ms
memory: 18964kb
input:
19446 20000 1 701024899 61691599 0 459112272 0 605953973 0 852714844 0 174821235 1 313026866 19060724 0 553043793 1 837260834 209473757 0 445224261 0 18895399 1 976728020 509710102 0 332645932 0 661618262 0 204178386 0 269435005 0 736889829 0 397995492 0 866964923 0 132403278 0 596284173 0 958984850...
output:
534451823 0 0 607037735 558413343 0 0 0 0 0 0 0 0 0 0 0 673258724 0 869080507 506727857 9843331 0 85465239 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 398060444 882747749 0 0 0 0 0 0 214087586 0 0 0 0 0 0 0 0 0 0 0 0 733471287 0 636321624 0 351918892 0 0 856397457 0 0 0 0 0 0 0 0 91532953 0 0 0 0 0 237024413 63...
result:
ok 20000 numbers
Subtask #6:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #31:
score: 30
Accepted
time: 880ms
memory: 70792kb
input:
99594 200000 0 792083461 0 914312025 0 34350651 0 767686614 0 126625954 1 469369269 944342533 0 612174706 0 659144535 0 980769871 0 11719240 0 686570452 0 557384020 0 775725208 1 206987845 317493823 0 549993972 0 243134305 0 50842360 2 694278935 105006374 564812234 0 273854368 0 949758784 0 80244234...
output:
109399968 0 0 0 448463153 0 0 818361960 238762152 489879263 532197351 0 0 0 0 0 143357594 0 0 0 0 0 0 0 0 0 0 737808980 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 848155620 0 788868258 0 0 0 547711349 0 0 0 0 0 0 0 0 0 0 0 0 0 0 338269278 0 575775483 0 532938132 0 0 0 0 611122990 718119560 0 0 0 ...
result:
ok 200000 numbers
Test #32:
score: 30
Accepted
time: 817ms
memory: 68872kb
input:
99035 200000 0 516279412 0 412939901 0 606838540 0 387878075 1 262965855 768053906 5 19202246 37691309 63031387 385686181 758382124 552090450 2 971931101 451423603 833655477 2 420564093 201427455 744193012 0 562042321 0 244312780 1 793149487 305896859 0 270808962 2 141955607 783349908 417999654 0 42...
output:
0 0 0 0 0 0 0 0 993301929 0 0 0 0 0 0 737055174 406546071 0 0 666458859 0 0 0 0 507321872 169036937 0 0 0 0 0 0 0 967598644 182481323 0 0 0 0 0 0 0 0 0 450225917 0 364239472 0 0 0 0 0 184083094 898158431 0 737677208 0 0 0 47593713 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 996953495 0 0 0 8084585...
result:
ok 200000 numbers
Test #33:
score: 30
Accepted
time: 613ms
memory: 57384kb
input:
99083 200000 9 812519718 737365909 60790048 110734972 345456242 716203655 119077807 648818873 468118712 147036529 1 297548567 794303861 5 641870110 181984618 69051204 758849582 714652096 396595861 1 560530303 275242004 0 574153100 0 317052463 0 480726959 3 110710840 830240927 248270237 978423303 0 5...
output:
0 0 567845892 29922025 0 0 0 0 134770615 0 0 0 0 0 0 0 0 0 471511799 0 0 0 0 0 0 0 0 0 0 0 0 0 85185078 0 0 581149537 0 540973163 0 0 0 747061501 751392383 0 0 594973285 0 123772660 0 0 0 0 0 0 0 0 304308252 260946625 121532287 0 340335526 0 0 0 0 0 0 0 0 0 0 0 148043643 0 0 0 0 575135327 0 54065753...
result:
ok 200000 numbers
Test #34:
score: 30
Accepted
time: 1427ms
memory: 108208kb
input:
99785 200000 0 280332852 0 463734447 0 171818841 0 299075569 0 863711022 0 907616285 0 234302886 1 977699188 129280311 0 460473318 0 570409123 0 29676746 0 906924939 0 929635560 0 444520539 0 61650377 1 176555744 745995937 0 767706179 0 697499158 1 968035736 79077206 0 853004807 0 669726083 0 917877...
output:
0 480380633 100067255 0 0 736885183 0 0 960940710 0 579705665 0 0 0 0 598371980 0 0 0 0 0 693279318 0 0 22276414 0 0 0 0 0 806866513 990455994 585969490 381728870 0 428502384 890759743 0 0 0 0 0 797184734 0 0 914101649 0 442980166 0 0 699124593 0 0 226141455 0 765484286 156198071 0 0 0 723454355 0 0...
result:
ok 200000 numbers
Test #35:
score: 30
Accepted
time: 678ms
memory: 60256kb
input:
99006 200000 2 697598318 566784456 782231144 0 637183338 3 892921153 312022999 614093234 489700823 6 565253346 400806749 352924076 615575261 636132162 769385558 185304555 1 354998163 679380727 0 808808987 0 914852081 0 609747589 4 53572246 687372077 109442084 787697001 647385656 4 212951526 24244475...
output:
873398887 0 908891814 0 0 0 0 854361978 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 681498313 0 0 0 0 0 0 0 0 192671131 0 0 0 0 0 0 775815056 0 886750665 0 0 0 0 256584318 170858682 0 0 0 0 0 61850051 0 0 0 0 0 0 0 0 0 29520959 0 0 866066650 0 0 0 895412488 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 200000 numbers
Test #36:
score: 30
Accepted
time: 589ms
memory: 53352kb
input:
98985 200000 0 969193375 0 511357294 0 328085529 1 205258866 499880016 0 933319732 0 609835434 0 135107485 0 781419224 0 620351326 0 740789220 0 179692891 1 505604147 785232172 0 748252583 1 963799862 977536089 0 946638152 0 503453397 0 783885375 0 243538347 1 358016785 386995362 0 282713402 0 29462...
output:
0 0 0 0 0 401910156 0 0 0 0 0 0 0 0 0 0 601764437 0 0 0 0 0 0 753618471 0 0 305995424 0 0 0 0 0 0 0 0 0 0 0 431722758 0 0 0 0 798679245 773158656 0 0 0 0 0 0 0 0 0 0 0 0 0 0 170839700 0 0 0 0 0 0 0 0 0 0 0 0 0 0 156648441 0 0 0 0 0 0 0 439657527 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 347352285 0 0 0 0 0 ...
result:
ok 200000 numbers
Test #37:
score: 30
Accepted
time: 630ms
memory: 58212kb
input:
99106 200000 0 536357478 1 248797118 129050430 1 106948594 292418714 0 510102794 1 133026708 722417074 0 180653240 0 446667653 0 287445048 0 661059497 0 594996611 0 819285540 0 783212723 0 210212100 0 693574734 0 112477560 0 674105046 0 248594760 1 158166781 850888375 0 497357910 1 640562644 6835468...
output:
0 0 0 0 0 0 0 0 957985443 0 0 0 0 0 0 0 966288616 0 520774584 0 0 0 321026238 0 0 0 0 0 513903889 162689619 0 0 0 0 0 265617770 0 97712317 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 953800844 0 0 0 0 0 0 0 0 0 0 424167855 0 0 0...
result:
ok 200000 numbers
Test #38:
score: 30
Accepted
time: 407ms
memory: 45064kb
input:
99337 200000 1 498475374 77807972 0 710939325 0 257489757 0 366384158 1 489698229 751337044 0 633357139 1 830049927 866194558 2 341614269 142470787 621653008 1 673980230 442738390 1 366325112 428366642 1 26626735 639931615 0 764633730 0 474395039 0 135657003 0 722380645 0 319814064 0 984404609 1 665...
output:
978464904 0 0 503368730 0 0 0 0 0 0 0 0 479532558 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 645577386 0 0 0 0 0 0 0 0 0 0 0 0 0 255376668 0 0 453568313 0 496966692 0 0 0 0 0 0 0 46766572 0 0 0 0 0 0 0 0 0 0 0 0 0 963187989...
result:
ok 200000 numbers
Test #39:
score: 30
Accepted
time: 652ms
memory: 60280kb
input:
99397 200000 1 908659187 39931868 0 672134567 2 102740510 36677225 150007181 2 471908611 266747812 357960206 0 136686904 1 551385776 27154055 6 897495677 293831234 982707521 723038522 356184574 855103517 336715204 0 60799780 0 77841372 3 798508674 561483859 147801908 665942476 0 545064278 1 19419329...
output:
0 0 0 0 0 0 0 347981445 556682855 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 708396072 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 209956118 0 0 0 0 0 0 0 0 606367784 0 0 0 0 0 0 0 0 0 0 368648402 0 0 0 0 0 65368737 634556670 0 0 0 467587270 0 877360716 0 0 0 518078588 0 0 0 0 0 476405426 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15193...
result:
ok 200000 numbers
Test #40:
score: 30
Accepted
time: 644ms
memory: 58020kb
input:
99251 200000 0 837618356 0 469241097 0 304116169 0 750862544 2 26173593 953672229 151599840 0 271279589 0 403113292 0 333427913 1 97867997 556460649 0 943168531 1 509903042 94841079 0 796070535 0 14009153 0 146895987 0 946947992 0 919251812 0 284637821 1 753226123 593010004 0 628694067 0 653161546 0...
output:
0 0 0 0 671158217 0 0 0 0 0 0 0 0 541497228 0 0 0 0 0 0 0 0 0 0 0 0 0 451481615 0 137067247 0 0 0 0 919959487 0 0 0 0 0 0 0 0 0 0 380863721 0 271452193 0 0 768517272 0 0 0 0 0 0 0 0 493731090 0 0 0 0 0 0 0 17031558 0 0 0 0 0 0 0 591218400 0 0 0 0 0 0 0 0 0 0 0 0 241982234 0 0 0 0 0 0 0 0 564614622 0...
result:
ok 200000 numbers
Test #41:
score: 30
Accepted
time: 646ms
memory: 59336kb
input:
99630 200000 0 5339176 0 183460101 0 78628974 0 71182183 1 821234975 144067318 0 956592536 0 82564025 1 334026285 237551854 0 154265800 0 260692099 0 260062211 1 456318703 276854147 1 587509429 4330857 0 381073041 0 675959015 0 965036457 0 283513233 2 316566027 40169150 897149637 2 770213563 2846924...
output:
309884962 263648364 548342103 189447330 403042313 0 164867241 51305764 463138099 0 0 63741792 0 42511729 0 486791755 0 102254495 0 0 0 0 656480709 0 0 0 680530049 686273532 998139721 0 0 0 783513253 720932489 0 812024439 938247438 847540531 669361421 0 601802190 0 990014943 517648770 672809095 96241...
result:
ok 200000 numbers
Test #42:
score: 30
Accepted
time: 952ms
memory: 77672kb
input:
99457 200000 0 520433982 0 600033942 0 597120011 1 131160787 64001098 1 573895343 649276549 0 195519651 0 475243851 0 289757468 0 804871132 0 666098884 1 231714454 628830730 0 890957706 0 83693875 0 301651579 0 291625927 0 404424239 0 181052960 1 536789543 288778943 0 166973270 1 345291754 449612874...
output:
0 0 0 0 304528688 0 0 766584610 0 0 0 0 656906535 777040558 0 269231403 0 757347049 0 0 447594777 0 881831292 914091245 0 0 0 403266514 741683002 526265855 0 0 0 0 967262076 0 856159414 0 0 0 782919249 327891282 0 572486461 0 0 179183639 735080713 682386725 0 0 0 0 0 0 0 8042811 82897394 446711502 1...
result:
ok 200000 numbers
Test #43:
score: 30
Accepted
time: 1345ms
memory: 102884kb
input:
99862 200000 0 329513920 0 456692223 0 389322229 0 711051456 1 621965494 55887520 0 787567565 0 84446280 0 826368108 1 453561473 162705929 0 468696179 0 57014528 1 423197442 911428275 1 331659854 508452048 0 47732231 0 510804785 0 620213653 0 403025819 0 14580380 0 901519255 0 283742795 1 181801236 ...
output:
0 839931845 157764911 0 0 215894684 46271392 44093675 493597065 400043755 456226878 178843285 0 0 0 125583360 556511446 782225218 336159443 0 48437262 91755146 356318949 0 982396681 325921161 888415778 237790380 670546292 0 0 217544729 0 859956339 441975647 0 759366102 0 28623977 849837651 238938530...
result:
ok 200000 numbers
Test #44:
score: 30
Accepted
time: 681ms
memory: 61844kb
input:
99826 200000 1 323757533 870721963 2 904066510 788467099 240486432 2 180249005 71060394 53648532 0 164816460 0 468389437 0 258522341 1 182854620 988856023 0 139155677 0 858918287 1 578115690 581264910 1 848138916 498790873 0 817795940 1 629829076 517122055 1 131196258 513843426 0 281344156 1 5802285...
output:
510251661 322843343 253640725 175763102 708684462 0 0 0 309152124 420069658 913416863 0 38362214 0 263332631 642129577 0 0 871646207 298848615 0 329074227 301650376 0 0 394836751 0 0 0 0 0 293433700 0 0 0 0 0 800387736 13640879 738620452 923035045 0 626487991 973833608 0 830455251 0 316717789 0 0 56...
result:
ok 200000 numbers
Test #45:
score: 30
Accepted
time: 655ms
memory: 60712kb
input:
99664 200000 1 670597153 137196970 0 448037909 2 395548978 50888515 225301038 1 906680594 111745385 0 645929612 0 376568237 0 996010090 0 312802967 1 241662879 805185907 0 137707642 0 574859364 0 21632077 0 350124558 0 761906213 1 413353455 722297338 1 105639958 81668975 1 442545161 130820256 0 9458...
output:
0 13298333 796411980 717176960 427401440 859158010 0 0 554287565 0 6804644 0 837333422 850263412 749968216 21290770 716013140 0 0 0 609035567 419341980 574978215 229688216 205887830 173899597 79717147 620548356 156657047 0 0 549142000 7967802 0 744725557 381309597 0 0 152201862 191766672 0 870908035...
result:
ok 200000 numbers
Test #46:
score: 30
Accepted
time: 602ms
memory: 57492kb
input:
99936 200000 1 838410326 559781352 1 15519661 512473228 0 686587663 0 652469143 0 961809442 0 902588805 2 520910408 493321502 493526367 0 307197602 0 512061775 0 463074640 0 795071099 0 448849408 0 522272325 0 867669253 0 791911631 0 796271393 0 800296456 0 285955113 1 743247418 779908196 0 51017333...
output:
0 0 0 305107306 379150599 42011282 0 0 0 161166073 0 0 864848153 295413953 0 0 256383330 699111476 0 364923213 0 0 0 381145587 0 210879721 0 466483292 0 228632730 781776361 0 609583689 38035139 0 0 766392384 496307425 872071527 327088206 0 901406598 0 82575915 0 186066196 976518077 838408449 0 34449...
result:
ok 200000 numbers
Test #47:
score: 30
Accepted
time: 818ms
memory: 67896kb
input:
99088 200000 0 364832553 0 178745750 0 835029198 1 279742807 102370162 0 834347368 0 612774133 0 180761166 1 379950497 157310301 0 29363731 0 509494437 0 700030867 1 935402282 883975840 0 982734964 0 279823368 0 654117002 0 396925115 0 8330908 0 8204127 0 175734468 0 292209557 0 530551196 0 24939281...
output:
84290885 172473711 320359781 0 686175639 997982871 739107336 0 70395054 651442000 212364566 606189810 340398452 369355651 0 0 753033235 0 0 241596491 31250190 937363693 657293623 0 283648025 863116720 740290686 0 703070193 0 0 649865908 260970173 628279215 0 0 552350281 692378378 829193962 26701348 ...
result:
ok 200000 numbers
Test #48:
score: 30
Accepted
time: 868ms
memory: 73216kb
input:
99145 200000 0 143560353 0 708439926 0 701452428 0 637315652 0 10858266 1 324024099 421464572 1 7867270 718774170 0 464413576 0 182983498 1 311377044 986639223 0 490148621 0 543909721 0 102531250 0 483589345 2 88597038 552846483 990387576 0 993560233 0 546852218 0 791201835 0 696249807 0 246306695 0...
output:
0 739694884 433769957 584558975 885259821 0 0 0 843472324 655955792 931400009 0 314207102 486068606 0 0 0 132839733 375394984 0 18557269 528832436 0 0 0 947710310 0 377197977 0 196747374 0 703143919 0 0 593537487 5538491 430096964 0 0 0 0 738126639 770283456 0 422226849 341610677 469499040 0 3008630...
result:
ok 200000 numbers
Test #49:
score: 30
Accepted
time: 1075ms
memory: 85424kb
input:
99917 200000 1 606379853 230564505 0 861782624 1 166045839 446984409 2 262143347 271529930 75070248 1 764120674 560497036 0 493657528 0 60011341 0 384737505 0 485851690 0 59804027 0 272031503 0 101931073 0 887059536 0 202260726 0 777511966 0 834899633 0 27259216 0 449327211 0 45993148 0 460191658 0 ...
output:
605186308 597933348 865908650 0 494051001 833085633 765000024 317367680 231872632 80637105 0 114289353 0 945516164 0 668977591 549708654 300760382 0 194940063 0 0 0 149218300 0 0 627379931 0 421969276 181354550 0 0 0 943014191 0 0 0 206946838 0 0 751545512 840917385 0 455228946 0 0 295557208 0 40024...
result:
ok 200000 numbers
Test #50:
score: 30
Accepted
time: 736ms
memory: 63720kb
input:
99626 200000 0 543722507 0 832417757 0 634572868 0 523056298 0 604006305 0 105205567 0 642477632 0 273861057 0 159049568 0 278889755 0 534451219 0 215637712 1 496543777 850957896 0 527887191 0 797572231 2 351423761 279337124 419541603 0 138972236 0 742639412 0 727952849 0 810781862 0 249581579 0 536...
output:
112541029 161741932 287403817 0 438982353 0 31544875 936722186 751598883 597267944 328798533 745429287 419961835 165995330 576022299 231729203 0 0 0 686554191 0 0 399196180 984422139 580466621 0 0 752262932 529783655 68016352 0 649283329 0 837279914 162398064 160608005 0 0 0 142098038 0 0 0 0 0 0 0 ...
result:
ok 200000 numbers
Test #51:
score: 30
Accepted
time: 431ms
memory: 47288kb
input:
100000 200000 0 613643917 0 835910163 0 418097458 1 813106042 240507736 0 563154711 2 915116833 242569780 645436195 1 983291419 722923451 2 275095780 639835018 487159272 0 363502753 0 864558407 0 52697997 1 99815226 844841329 0 174326710 1 806922141 55304067 2 804584045 470065735 376654165 0 3357850...
output:
0 314701272 301367246 0 0 0 307274596 0 979251102 0 0 0 0 0 0 0 0 0 0 429196314 0 0 0 0 105273277 0 0 950508916 306261739 247158638 0 0 443091520 0 0 0 778682554 0 0 0 149346952 0 871501201 0 0 0 127247196 0 0 0 0 0 198153970 893188252 0 841579618 24284813 537727232 616030760 0 0 0 860476381 5104688...
result:
ok 200000 numbers
Test #52:
score: 30
Accepted
time: 658ms
memory: 57096kb
input:
100000 200000 0 654076004 0 384031444 0 119374495 0 277579093 1 85876027 638148431 0 936480874 0 337004560 0 601574248 2 841095919 465239266 978449729 0 612063963 0 944928965 0 677239581 0 381653436 0 840246095 0 88260192 0 494499583 1 651377177 499867035 0 43926530 0 835699069 0 100921766 0 5710994...
output:
659159881 0 0 244713927 0 38053686 0 370345134 0 676351040 195874172 331050819 0 311975954 0 0 0 0 547003239 0 0 784593602 10749736 810352369 281275711 0 849350910 0 0 0 0 0 860912575 499058071 0 0 0 0 472871922 0 0 0 0 0 0 0 0 382020240 0 0 0 0 0 501714412 489877411 677514091 0 382886760 0 0 0 0 0 ...
result:
ok 200000 numbers
Test #53:
score: 30
Accepted
time: 363ms
memory: 43852kb
input:
100000 200000 0 767950655 0 819206798 0 632776873 0 615458376 0 748952719 0 164743123 0 484317825 0 364077066 0 416857111 0 21162008 0 892795892 0 54757732 0 501046447 0 795792626 0 18991377 0 37548129 0 522283271 0 522400896 0 27035995 0 207431962 0 960915263 0 289342447 0 903308477 0 986811346 1 5...
output:
0 0 0 0 320911640 0 0 0 835380661 0 101129300 0 0 436510016 0 721709531 0 0 532297750 910683734 0 0 0 482614108 0 0 0 404027771 0 0 0 472509567 0 421942867 0 813473143 175018943 0 0 139332966 0 0 0 0 0 831264950 0 0 956587496 479700944 0 0 0 472306267 0 0 896405196 0 0 0 0 0 0 0 44420065 674247742 0...
result:
ok 200000 numbers
Test #54:
score: 30
Accepted
time: 650ms
memory: 61856kb
input:
100000 200000 80 975550954 194913535 93700686 603729067 514440779 5168754 493927441 225485222 367936123 66713098 693546661 995088484 849731735 241941370 756949641 477954618 773614993 153565165 321282091 75959417 436627529 864112020 870058819 110164879 875241154 473099607 381812633 879132931 95273234...
output:
0 421673387 618293885 0 569777033 761083826 0 0 143262552 0 252024071 168883593 625390897 0 0 885716630 446743153 0 748901923 0 0 958947377 381449865 0 0 0 0 0 0 338243090 0 0 306769426 0 492995267 642640342 0 625868541 0 264120975 0 601461549 528185255 762292312 0 0 0 193716429 0 235099016 0 0 9188...
result:
ok 200000 numbers
Test #55:
score: 30
Accepted
time: 1361ms
memory: 107468kb
input:
100000 200000 1 370861671 597066317 1 279824219 835160176 2 890487447 312744954 293454271 0 256787799 0 525148622 0 310156426 1 30788965 106411304 0 860888126 0 13034841 0 91907701 0 96687299 0 448250210 1 316241974 721488419 2 317152672 491377577 192877359 0 830289753 0 769751867 0 119369072 0 2154...
output:
0 495342720 0 932168052 0 597533739 0 0 95979658 0 589148997 271163162 861440993 0 38549103 868360666 89387346 0 0 378468426 0 0 0 0 0 549989891 839865697 0 733467239 0 0 740630196 575730895 221141247 0 223984070 417737077 0 0 0 383572216 727210228 0 996006344 0 0 0 0 0 0 115192594 99462280 0 209476...
result:
ok 200000 numbers
Test #56:
score: 30
Accepted
time: 492ms
memory: 51280kb
input:
100000 200000 0 855935515 0 503029155 0 530279261 0 946473936 0 32581962 0 601598388 0 288273127 0 425515309 0 728814403 0 797556500 0 70386731 0 693458131 0 178352976 0 934593143 0 810333890 0 650702505 0 132404762 0 557444214 0 187801602 0 713129003 0 206777009 0 579160604 0 51113448 0 786951044 0...
output:
439964729 0 101250422 377604701 0 928328203 0 311197502 0 761687584 0 0 365258170 0 939530105 191412194 0 0 879112407 536002240 0 369080761 695996586 464890584 0 0 0 0 0 860862436 0 0 791830786 52010983 0 0 0 0 0 903621456 340505284 0 0 0 0 0 0 0 0 157762756 730657042 406293120 247221862 0 0 0 0 0 8...
result:
ok 200000 numbers
Test #57:
score: 30
Accepted
time: 1121ms
memory: 93612kb
input:
100000 200000 0 957889022 0 214078695 1 483864879 225025140 0 272321791 1 186288580 21482959 0 837319618 0 63552234 0 124514667 0 266485699 0 681756899 1 73283727 713211035 0 208369034 0 527424469 0 853819875 1 318538042 411538896 0 238374843 1 401815602 35413471 0 679451288 0 721170212 0 237460435 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 29283727 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 200000 numbers
Test #58:
score: 30
Accepted
time: 360ms
memory: 42312kb
input:
100000 200000 0 237677757 0 445038744 1 48499603 865005690 0 80453651 1 872325575 771904118 0 357606035 0 35698382 0 670168087 1 68812218 129958009 0 727178484 3 669452613 594874653 257476740 684536854 0 933422955 2 26415111 487769382 950606834 0 822838477 0 395410818 1 464093805 146648967 0 5402800...
output:
0 142431692 0 0 64525901 487482466 0 0 623335869 0 0 0 44757631 0 0 0 377565055 258331352 69775601 653608658 0 0 0 616970041 0 0 686456182 0 0 0 0 0 654294845 0 314063149 0 669527678 257486799 0 784911411 0 116961556 0 0 265128386 0 0 0 786118866 0 839678272 0 0 0 0 886976855 754239384 0 379664936 5...
result:
ok 200000 numbers
Test #59:
score: 30
Accepted
time: 665ms
memory: 61752kb
input:
100000 200000 0 564710724 0 208139081 84 824126092 287147669 859164352 91151335 630815103 51548342 878003285 701830355 258617205 894838138 961514745 511239843 848675884 55652377 908595648 210679303 878326125 349020875 810714103 246980554 33781344 344616238 841820124 279994891 579099712 812328036 667...
output:
33767043 0 114715016 0 0 689242238 0 0 0 0 29286069 249435181 0 0 0 111465282 830221170 0 571082250 0 0 710434908 0 0 0 820068292 562220327 0 233440294 0 0 0 0 0 289233587 0 102216699 0 557677325 0 629810979 0 0 0 670602664 0 626612356 0 0 0 0 975935882 937193482 791983888 560865529 0 171942466 0 0 ...
result:
ok 200000 numbers
Test #60:
score: 30
Accepted
time: 586ms
memory: 55700kb
input:
100000 200000 0 158275260 1 287953086 578797831 0 474574496 0 190421636 1 828207062 780536839 0 73629262 0 127353181 0 399256593 2 581386154 715563215 268353972 1 387565681 225637914 1 640238681 118929274 0 297084940 1 557699324 177235182 0 25121062 0 722998173 1 597523931 149714293 0 108543196 1 72...
output:
931454750 0 741621372 0 508359232 0 0 0 268403560 0 317163570 0 0 0 0 417499296 0 857602890 0 0 769309753 712999564 0 243212495 169057700 405270682 0 456986014 0 0 0 0 0 253419485 0 703169565 17102526 0 611555671 607560013 0 458232888 0 0 0 0 0 0 15394385 0 137706560 334513057 0 0 0 633320663 129680...
result:
ok 200000 numbers