QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719709 | #9608. 皮鞋的多项式 | peaneval_kala | 30 | 1542ms | 94568kb | C++23 | 17.2kb | 2024-11-07 08:18:09 | 2024-11-07 08:18:10 |
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{};
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 void merge(int x, int y) {
f[x] *= f[y];
if (f[x].size() > B || (id[x] && id[y])) {
++cc;
big[cc] = big[id[x]] * big[id[y]] * f[x];
f[x] = {1};
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) / 2));
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);
// 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: 17ms
memory: 15064kb
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: 18ms
memory: 15252kb
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: 15ms
memory: 14836kb
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: 26ms
memory: 15420kb
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: 19ms
memory: 15244kb
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: 38ms
memory: 22044kb
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: 37ms
memory: 22124kb
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: 0
Time Limit Exceeded
Test #8:
score: 0
Time Limit Exceeded
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:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #13:
score: 20
Accepted
time: 1542ms
memory: 94568kb
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: 0
Time Limit Exceeded
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:
result:
Subtask #5:
score: 20
Accepted
Test #21:
score: 20
Accepted
time: 245ms
memory: 28920kb
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: 165ms
memory: 24468kb
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: 308ms
memory: 30440kb
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: 249ms
memory: 27300kb
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: 292ms
memory: 29724kb
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: 294ms
memory: 31284kb
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: 386ms
memory: 37588kb
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: 199ms
memory: 24896kb
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: 6ms
memory: 17844kb
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: 159ms
memory: 23272kb
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: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%