QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #279125 | #7563. Fun on Tree | maspy | AC ✓ | 1184ms | 49360kb | C++20 | 33.8kb | 2023-12-08 11:31:13 | 2023-12-08 11:31:13 |
Judging History
answer
#line 1 "library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr ll infty<ll> = ll(infty<int>) * infty<int> * 2;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * infty<ll>;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vv(type, name, h, ...) \
vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) \
vector<vector<vector<type>>> name( \
h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name( \
a, vector<vector<vector<type>>>( \
b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_subset(t, s) \
for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define stoi stoll
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_mod_2(int x) { return __builtin_parity(x); }
int popcnt_mod_2(u32 x) { return __builtin_parity(x); }
int popcnt_mod_2(ll x) { return __builtin_parityll(x); }
int popcnt_mod_2(u64 x) { return __builtin_parityll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T>
T floor(T a, T b) {
return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <typename T, typename U>
T SUM(const vector<U> &A) {
T sm = 0;
for (auto &&a: A) sm += a;
return sm;
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) \
sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
template <typename T>
T POP(deque<T> &que) {
T a = que.front();
que.pop_front();
return a;
}
template <typename T>
T POP(pq<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(pqg<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(vc<T> &que) {
T a = que.back();
que.pop_back();
return a;
}
template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
if (check_ok) assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
(check(x) ? ok : ng) = x;
}
return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
FOR(iter) {
double x = (ok + ng) / 2;
(check(x) ? ok : ng) = x;
}
return (ok + ng) / 2;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
vc<int> A(S.size());
FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
return A;
}
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
int N = A.size();
vector<T> B(N + 1);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ids(len(A));
iota(all(ids), 0);
sort(all(ids),
[&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ids;
}
// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
vc<T> B(len(I));
FOR(i, len(I)) B[i] = A[I[i]];
return B;
}
#endif
#line 1 "library/other/io.hpp"
#define FASTIO
#include <unistd.h>
// https://judge.yosupo.jp/submission/21623
namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
char out[100];
// pointer of ibuf, obuf
uint32_t pil = 0, pir = 0, por = 0;
struct Pre {
char num[10000][4];
constexpr Pre() : num() {
for (int i = 0; i < 10000; i++) {
int n = i;
for (int j = 3; j >= 0; j--) {
num[i][j] = n % 10 | '0';
n /= 10;
}
}
}
} constexpr pre;
inline void load() {
memcpy(ibuf, ibuf + pil, pir - pil);
pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
pil = 0;
if (pir < SZ) ibuf[pir++] = '\n';
}
inline void flush() {
fwrite(obuf, 1, por, stdout);
por = 0;
}
void rd(char &c) {
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
}
void rd(string &x) {
x.clear();
char c;
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
do {
x += c;
if (pil == pir) load();
c = ibuf[pil++];
} while (!isspace(c));
}
template <typename T>
void rd_real(T &x) {
string s;
rd(s);
x = stod(s);
}
template <typename T>
void rd_integer(T &x) {
if (pil + 100 > pir) load();
char c;
do
c = ibuf[pil++];
while (c < '-');
bool minus = 0;
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (c == '-') { minus = 1, c = ibuf[pil++]; }
}
x = 0;
while ('0' <= c) { x = x * 10 + (c & 15), c = ibuf[pil++]; }
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (minus) x = -x;
}
}
void rd(int &x) { rd_integer(x); }
void rd(ll &x) { rd_integer(x); }
void rd(i128 &x) { rd_integer(x); }
void rd(u32 &x) { rd_integer(x); }
void rd(u64 &x) { rd_integer(x); }
void rd(u128 &x) { rd_integer(x); }
void rd(double &x) { rd_real(x); }
void rd(long double &x) { rd_real(x); }
void rd(f128 &x) { rd_real(x); }
template <class T, class U>
void rd(pair<T, U> &p) {
return rd(p.first), rd(p.second);
}
template <size_t N = 0, typename T>
void rd_tuple(T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
rd(x);
rd_tuple<N + 1>(t);
}
}
template <class... T>
void rd(tuple<T...> &tpl) {
rd_tuple(tpl);
}
template <size_t N = 0, typename T>
void rd(array<T, N> &x) {
for (auto &d: x) rd(d);
}
template <class T>
void rd(vc<T> &x) {
for (auto &d: x) rd(d);
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
rd(h), read(t...);
}
void wt(const char c) {
if (por == SZ) flush();
obuf[por++] = c;
}
void wt(const string s) {
for (char c: s) wt(c);
}
void wt(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) wt(s[i]);
}
template <typename T>
void wt_integer(T x) {
if (por > SZ - 100) flush();
if (x < 0) { obuf[por++] = '-', x = -x; }
int outi;
for (outi = 96; x >= 10000; outi -= 4) {
memcpy(out + outi, pre.num[x % 10000], 4);
x /= 10000;
}
if (x >= 1000) {
memcpy(obuf + por, pre.num[x], 4);
por += 4;
} else if (x >= 100) {
memcpy(obuf + por, pre.num[x] + 1, 3);
por += 3;
} else if (x >= 10) {
int q = (x * 103) >> 10;
obuf[por] = q | '0';
obuf[por + 1] = (x - q * 10) | '0';
por += 2;
} else
obuf[por++] = x | '0';
memcpy(obuf + por, out + outi + 4, 96 - outi);
por += 96 - outi;
}
template <typename T>
void wt_real(T x) {
ostringstream oss;
oss << fixed << setprecision(15) << double(x);
string s = oss.str();
wt(s);
}
void wt(int x) { wt_integer(x); }
void wt(ll x) { wt_integer(x); }
void wt(i128 x) { wt_integer(x); }
void wt(u32 x) { wt_integer(x); }
void wt(u64 x) { wt_integer(x); }
void wt(u128 x) { wt_integer(x); }
void wt(double x) { wt_real(x); }
void wt(long double x) { wt_real(x); }
void wt(f128 x) { wt_real(x); }
template <class T, class U>
void wt(const pair<T, U> val) {
wt(val.first);
wt(' ');
wt(val.second);
}
template <size_t N = 0, typename T>
void wt_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) { wt(' '); }
const auto x = std::get<N>(t);
wt(x);
wt_tuple<N + 1>(t);
}
}
template <class... T>
void wt(tuple<T...> tpl) {
wt_tuple(tpl);
}
template <class T, size_t S>
void wt(const array<T, S> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
template <class T>
void wt(const vector<T> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
wt(head);
if (sizeof...(Tail)) wt(' ');
print(forward<Tail>(tail)...);
}
// gcc expansion. called automaticall after main.
void __attribute__((destructor)) _d() { flush(); }
} // namespace fastio
using fastio::read;
using fastio::print;
using fastio::flush;
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define U32(...) \
u32 __VA_ARGS__; \
read(__VA_ARGS__)
#define U64(...) \
u64 __VA_ARGS__; \
read(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
read(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
read(name)
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 3 "main.cpp"
#line 2 "library/graph/tree.hpp"
#line 2 "library/graph/base.hpp"
template <typename T>
struct Edge {
int frm, to;
T cost;
int id;
};
template <typename T = int, bool directed = false>
struct Graph {
static constexpr bool is_directed = directed;
int N, M;
using cost_type = T;
using edge_type = Edge<T>;
vector<edge_type> edges;
vector<int> indptr;
vector<edge_type> csr_edges;
vc<int> vc_deg, vc_indeg, vc_outdeg;
bool prepared;
class OutgoingEdges {
public:
OutgoingEdges(const Graph* G, int l, int r) : G(G), l(l), r(r) {}
const edge_type* begin() const {
if (l == r) { return 0; }
return &G->csr_edges[l];
}
const edge_type* end() const {
if (l == r) { return 0; }
return &G->csr_edges[r];
}
private:
const Graph* G;
int l, r;
};
bool is_prepared() { return prepared; }
Graph() : N(0), M(0), prepared(0) {}
Graph(int N) : N(N), M(0), prepared(0) {}
void build(int n) {
N = n, M = 0;
prepared = 0;
edges.clear();
indptr.clear();
csr_edges.clear();
vc_deg.clear();
vc_indeg.clear();
vc_outdeg.clear();
}
void add(int frm, int to, T cost = 1, int i = -1) {
assert(!prepared);
assert(0 <= frm && 0 <= to && to < N);
if (i == -1) i = M;
auto e = edge_type({frm, to, cost, i});
edges.eb(e);
++M;
}
#ifdef FASTIO
// wt, off
void read_tree(bool wt = false, int off = 1) { read_graph(N - 1, wt, off); }
void read_graph(int M, bool wt = false, int off = 1) {
for (int m = 0; m < M; ++m) {
INT(a, b);
a -= off, b -= off;
if (!wt) {
add(a, b);
} else {
T c;
read(c);
add(a, b, c);
}
}
build();
}
#endif
void build() {
assert(!prepared);
prepared = true;
indptr.assign(N + 1, 0);
for (auto&& e: edges) {
indptr[e.frm + 1]++;
if (!directed) indptr[e.to + 1]++;
}
for (int v = 0; v < N; ++v) { indptr[v + 1] += indptr[v]; }
auto counter = indptr;
csr_edges.resize(indptr.back() + 1);
for (auto&& e: edges) {
csr_edges[counter[e.frm]++] = e;
if (!directed)
csr_edges[counter[e.to]++] = edge_type({e.to, e.frm, e.cost, e.id});
}
}
OutgoingEdges operator[](int v) const {
assert(prepared);
return {this, indptr[v], indptr[v + 1]};
}
vc<int> deg_array() {
if (vc_deg.empty()) calc_deg();
return vc_deg;
}
pair<vc<int>, vc<int>> deg_array_inout() {
if (vc_indeg.empty()) calc_deg_inout();
return {vc_indeg, vc_outdeg};
}
int deg(int v) {
if (vc_deg.empty()) calc_deg();
return vc_deg[v];
}
int in_deg(int v) {
if (vc_indeg.empty()) calc_deg_inout();
return vc_indeg[v];
}
int out_deg(int v) {
if (vc_outdeg.empty()) calc_deg_inout();
return vc_outdeg[v];
}
#ifdef FASTIO
void debug() {
print("Graph");
if (!prepared) {
print("frm to cost id");
for (auto&& e: edges) print(e.frm, e.to, e.cost, e.id);
} else {
print("indptr", indptr);
print("frm to cost id");
FOR(v, N) for (auto&& e: (*this)[v]) print(e.frm, e.to, e.cost, e.id);
}
}
#endif
vc<int> new_idx;
vc<bool> used_e;
// G における頂点 V[i] が、新しいグラフで i になるようにする
// {G, es}
Graph<T, directed> rearrange(vc<int> V, bool keep_eid = 0) {
if (len(new_idx) != N) new_idx.assign(N, -1);
if (len(used_e) != M) used_e.assign(M, 0);
int n = len(V);
FOR(i, n) new_idx[V[i]] = i;
Graph<T, directed> G(n);
vc<int> history;
FOR(i, n) {
for (auto&& e: (*this)[V[i]]) {
if (used_e[e.id]) continue;
int a = e.frm, b = e.to;
if (new_idx[a] != -1 && new_idx[b] != -1) {
history.eb(e.id);
used_e[e.id] = 1;
int eid = (keep_eid ? e.id : -1);
G.add(new_idx[a], new_idx[b], e.cost, eid);
}
}
}
FOR(i, n) new_idx[V[i]] = -1;
for (auto&& eid: history) used_e[eid] = 0;
G.build();
return G;
}
private:
void calc_deg() {
assert(vc_deg.empty());
vc_deg.resize(N);
for (auto&& e: edges) vc_deg[e.frm]++, vc_deg[e.to]++;
}
void calc_deg_inout() {
assert(vc_indeg.empty());
vc_indeg.resize(N);
vc_outdeg.resize(N);
for (auto&& e: edges) { vc_indeg[e.to]++, vc_outdeg[e.frm]++; }
}
};
#line 4 "library/graph/tree.hpp"
// HLD euler tour をとっていろいろ。
template <typename GT>
struct Tree {
using Graph_type = GT;
GT &G;
using WT = typename GT::cost_type;
int N;
vector<int> LID, RID, head, V, parent, VtoE;
vc<int> depth;
vc<WT> depth_weighted;
Tree(GT &G, int r = 0, bool hld = 1) : G(G) { build(r, hld); }
void build(int r = 0, bool hld = 1) {
if (r == -1) return; // build を遅延したいとき
N = G.N;
LID.assign(N, -1), RID.assign(N, -1), head.assign(N, r);
V.assign(N, -1), parent.assign(N, -1), VtoE.assign(N, -1);
depth.assign(N, -1), depth_weighted.assign(N, 0);
assert(G.is_prepared());
int t1 = 0;
dfs_sz(r, -1, hld);
dfs_hld(r, t1);
}
void dfs_sz(int v, int p, bool hld) {
auto &sz = RID;
parent[v] = p;
depth[v] = (p == -1 ? 0 : depth[p] + 1);
sz[v] = 1;
int l = G.indptr[v], r = G.indptr[v + 1];
auto &csr = G.csr_edges;
// 使う辺があれば先頭にする
for (int i = r - 2; i >= l; --i) {
if (hld && depth[csr[i + 1].to] == -1) swap(csr[i], csr[i + 1]);
}
int hld_sz = 0;
for (int i = l; i < r; ++i) {
auto e = csr[i];
if (depth[e.to] != -1) continue;
depth_weighted[e.to] = depth_weighted[v] + e.cost;
VtoE[e.to] = e.id;
dfs_sz(e.to, v, hld);
sz[v] += sz[e.to];
if (hld && chmax(hld_sz, sz[e.to]) && l < i) { swap(csr[l], csr[i]); }
}
}
void dfs_hld(int v, int ×) {
LID[v] = times++;
RID[v] += LID[v];
V[LID[v]] = v;
bool heavy = true;
for (auto &&e: G[v]) {
if (depth[e.to] <= depth[v]) continue;
head[e.to] = (heavy ? head[v] : e.to);
heavy = false;
dfs_hld(e.to, times);
}
}
vc<int> heavy_path_at(int v) {
vc<int> P = {v};
while (1) {
int a = P.back();
for (auto &&e: G[a]) {
if (e.to != parent[a] && head[e.to] == v) {
P.eb(e.to);
break;
}
}
if (P.back() == a) break;
}
return P;
}
int heavy_child(int v) {
int k = LID[v] + 1;
if (k == N) return -1;
int w = V[k];
return (parent[w] == v ? w : -1);
}
int e_to_v(int eid) {
auto e = G.edges[eid];
return (parent[e.frm] == e.to ? e.frm : e.to);
}
int v_to_e(int v) { return VtoE[v]; }
int ELID(int v) { return 2 * LID[v] - depth[v]; }
int ERID(int v) { return 2 * RID[v] - depth[v] - 1; }
// 目標地点へ進む個数が k
int LA(int v, int k) {
assert(k <= depth[v]);
while (1) {
int u = head[v];
if (LID[v] - k >= LID[u]) return V[LID[v] - k];
k -= LID[v] - LID[u] + 1;
v = parent[u];
}
}
int la(int u, int v) { return LA(u, v); }
int LCA(int u, int v) {
for (;; v = parent[head[v]]) {
if (LID[u] > LID[v]) swap(u, v);
if (head[u] == head[v]) return u;
}
}
// root を根とした場合の lca
int LCA_root(int u, int v, int root) {
return LCA(u, v) ^ LCA(u, root) ^ LCA(v, root);
}
int lca(int u, int v) { return LCA(u, v); }
int lca_root(int u, int v, int root) { return LCA_root(u, v, root); }
int subtree_size(int v, int root = -1) {
if (root == -1) return RID[v] - LID[v];
if (v == root) return N;
int x = jump(v, root, 1);
if (in_subtree(v, x)) return RID[v] - LID[v];
return N - RID[x] + LID[x];
}
int dist(int a, int b) {
int c = LCA(a, b);
return depth[a] + depth[b] - 2 * depth[c];
}
WT dist_weighted(int a, int b) {
int c = LCA(a, b);
return depth_weighted[a] + depth_weighted[b] - WT(2) * depth_weighted[c];
}
// a is in b
bool in_subtree(int a, int b) { return LID[b] <= LID[a] && LID[a] < RID[b]; }
int jump(int a, int b, ll k) {
if (k == 1) {
if (a == b) return -1;
return (in_subtree(b, a) ? LA(b, depth[b] - depth[a] - 1) : parent[a]);
}
int c = LCA(a, b);
int d_ac = depth[a] - depth[c];
int d_bc = depth[b] - depth[c];
if (k > d_ac + d_bc) return -1;
if (k <= d_ac) return LA(a, k);
return LA(b, d_ac + d_bc - k);
}
vc<int> collect_child(int v) {
vc<int> res;
for (auto &&e: G[v])
if (e.to != parent[v]) res.eb(e.to);
return res;
}
vc<int> collect_light(int v) {
vc<int> res;
bool skip = true;
for (auto &&e: G[v])
if (e.to != parent[v]) {
if (!skip) res.eb(e.to);
skip = false;
}
return res;
}
vc<pair<int, int>> get_path_decomposition(int u, int v, bool edge) {
// [始点, 終点] の"閉"区間列。
vc<pair<int, int>> up, down;
while (1) {
if (head[u] == head[v]) break;
if (LID[u] < LID[v]) {
down.eb(LID[head[v]], LID[v]);
v = parent[head[v]];
} else {
up.eb(LID[u], LID[head[u]]);
u = parent[head[u]];
}
}
if (LID[u] < LID[v]) down.eb(LID[u] + edge, LID[v]);
elif (LID[v] + edge <= LID[u]) up.eb(LID[u], LID[v] + edge);
reverse(all(down));
up.insert(up.end(), all(down));
return up;
}
vc<int> restore_path(int u, int v) {
vc<int> P;
for (auto &&[a, b]: get_path_decomposition(u, v, 0)) {
if (a <= b) {
FOR(i, a, b + 1) P.eb(V[i]);
} else {
FOR_R(i, b, a + 1) P.eb(V[i]);
}
}
return P;
}
};
#line 2 "library/alg/monoid/max_idx.hpp"
template <typename T, bool tie_is_left = true>
struct Monoid_Max_Idx {
using value_type = pair<T, int>;
using X = value_type;
static X op(X x, X y) {
if (x.fi > y.fi) return x;
if (x.fi < y.fi) return y;
if (x.se > y.se) swap(x, y);
return (tie_is_left ? x : y);
}
static constexpr X unit() { return {-infty<T>, -1}; }
static constexpr bool commute = true;
};
#line 2 "library/alg/monoid/add.hpp"
template <typename X>
struct Monoid_Add {
using value_type = X;
static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
static constexpr X inverse(const X &x) noexcept { return -x; }
static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
static constexpr X unit() { return X(0); }
static constexpr bool commute = true;
};
#line 3 "library/alg/acted_monoid/maxidx_add.hpp"
template <typename E, bool tie_is_left = true>
struct ActedMonoid_MaxIdx_Add {
using Monoid_X = Monoid_Max_Idx<E, tie_is_left>;
using Monoid_A = Monoid_Add<E>;
using X = typename Monoid_X::value_type;
using A = typename Monoid_A::value_type;
static constexpr X act(const X &x, const A &a, const ll &size) {
if (x.fi == -infty<E>) return x;
return {x.fi + a, x.se};
}
};
#line 2 "library/ds/segtree/segtree.hpp"
template <class Monoid>
struct SegTree {
using MX = Monoid;
using X = typename MX::value_type;
using value_type = X;
vc<X> dat;
int n, log, size;
SegTree() {}
SegTree(int n) { build(n); }
template <typename F>
SegTree(int n, F f) {
build(n, f);
}
SegTree(const vc<X>& v) { build(v); }
void build(int m) {
build(m, [](int i) -> X { return MX::unit(); });
}
void build(const vc<X>& v) {
build(len(v), [&](int i) -> X { return v[i]; });
}
template <typename F>
void build(int m, F f) {
n = m, log = 1;
while ((1 << log) < n) ++log;
size = 1 << log;
dat.assign(size << 1, MX::unit());
FOR(i, n) dat[size + i] = f(i);
FOR_R(i, 1, size) update(i);
}
X get(int i) { return dat[size + i]; }
vc<X> get_all() { return {dat.begin() + size, dat.begin() + size + n}; }
void update(int i) { dat[i] = Monoid::op(dat[2 * i], dat[2 * i + 1]); }
void set(int i, const X& x) {
assert(i < n);
dat[i += size] = x;
while (i >>= 1) update(i);
}
void multiply(int i, const X& x) {
assert(i < n);
i += size;
dat[i] = Monoid::op(dat[i], x);
while (i >>= 1) update(i);
}
X prod(int L, int R) {
assert(0 <= L && L <= R && R <= n);
X vl = Monoid::unit(), vr = Monoid::unit();
L += size, R += size;
while (L < R) {
if (L & 1) vl = Monoid::op(vl, dat[L++]);
if (R & 1) vr = Monoid::op(dat[--R], vr);
L >>= 1, R >>= 1;
}
return Monoid::op(vl, vr);
}
X prod_all() { return dat[1]; }
template <class F>
int max_right(F check, int L) {
assert(0 <= L && L <= n && check(Monoid::unit()));
if (L == n) return n;
L += size;
X sm = Monoid::unit();
do {
while (L % 2 == 0) L >>= 1;
if (!check(Monoid::op(sm, dat[L]))) {
while (L < size) {
L = 2 * L;
if (check(Monoid::op(sm, dat[L]))) { sm = Monoid::op(sm, dat[L++]); }
}
return L - size;
}
sm = Monoid::op(sm, dat[L++]);
} while ((L & -L) != L);
return n;
}
template <class F>
int min_left(F check, int R) {
assert(0 <= R && R <= n && check(Monoid::unit()));
if (R == 0) return 0;
R += size;
X sm = Monoid::unit();
do {
--R;
while (R > 1 && (R % 2)) R >>= 1;
if (!check(Monoid::op(dat[R], sm))) {
while (R < size) {
R = 2 * R + 1;
if (check(Monoid::op(dat[R], sm))) { sm = Monoid::op(dat[R--], sm); }
}
return R + 1 - size;
}
sm = Monoid::op(dat[R], sm);
} while ((R & -R) != R);
return 0;
}
// prod_{l<=i<r} A[i xor x]
X xor_prod(int l, int r, int xor_val) {
static_assert(Monoid::commute);
X x = Monoid::unit();
for (int k = 0; k < log + 1; ++k) {
if (l >= r) break;
if (l & 1) { x = Monoid::op(x, dat[(size >> k) + ((l++) ^ xor_val)]); }
if (r & 1) { x = Monoid::op(x, dat[(size >> k) + ((--r) ^ xor_val)]); }
l /= 2, r /= 2, xor_val /= 2;
}
return x;
}
};
#line 2 "library/ds/segtree/lazy_segtree.hpp"
template <typename ActedMonoid>
struct Lazy_SegTree {
using AM = ActedMonoid;
using MX = typename AM::Monoid_X;
using MA = typename AM::Monoid_A;
using X = typename MX::value_type;
using A = typename MA::value_type;
int n, log, size;
vc<X> dat;
vc<A> laz;
Lazy_SegTree() {}
Lazy_SegTree(int n) { build(n); }
template <typename F>
Lazy_SegTree(int n, F f) {
build(n, f);
}
Lazy_SegTree(const vc<X>& v) { build(v); }
void build(int m) {
build(m, [](int i) -> X { return MX::unit(); });
}
void build(const vc<X>& v) {
build(len(v), [&](int i) -> X { return v[i]; });
}
template <typename F>
void build(int m, F f) {
n = m, log = 1;
while ((1 << log) < n) ++log;
size = 1 << log;
dat.assign(size << 1, MX::unit());
laz.assign(size, MA::unit());
FOR(i, n) dat[size + i] = f(i);
FOR_R(i, 1, size) update(i);
}
void update(int k) { dat[k] = MX::op(dat[2 * k], dat[2 * k + 1]); }
void set(int p, X x) {
assert(0 <= p && p < n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
dat[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
void multiply(int p, const X& x) {
assert(0 <= p && p < n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
dat[p] = MX::op(dat[p], x);
for (int i = 1; i <= log; i++) update(p >> i);
}
X get(int p) {
assert(0 <= p && p < n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return dat[p];
}
vc<X> get_all() {
FOR(k, 1, size) { push(k); }
return {dat.begin() + size, dat.begin() + size + n};
}
X prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) return MX::unit();
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);
}
X xl = MX::unit(), xr = MX::unit();
while (l < r) {
if (l & 1) xl = MX::op(xl, dat[l++]);
if (r & 1) xr = MX::op(dat[--r], xr);
l >>= 1, r >>= 1;
}
return MX::op(xl, xr);
}
X prod_all() { return dat[1]; }
void apply(int l, int r, A a) {
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) apply_at(l++, a);
if (r & 1) apply_at(--r, a);
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 <typename F>
int max_right(const F check, int l) {
assert(0 <= l && l <= n);
assert(check(MX::unit()));
if (l == n) return n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
X sm = MX::unit();
do {
while (l % 2 == 0) l >>= 1;
if (!check(MX::op(sm, dat[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (check(MX::op(sm, dat[l]))) { sm = MX::op(sm, dat[l++]); }
}
return l - size;
}
sm = MX::op(sm, dat[l++]);
} while ((l & -l) != l);
return n;
}
template <typename F>
int min_left(const F check, int r) {
assert(0 <= r && r <= n);
assert(check(MX::unit()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
X sm = MX::unit();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!check(MX::op(dat[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (check(MX::op(dat[r], sm))) { sm = MX::op(dat[r--], sm); }
}
return r + 1 - size;
}
sm = MX::op(dat[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
void apply_at(int k, A a) {
ll sz = 1 << (log - topbit(k));
dat[k] = AM::act(dat[k], a, sz);
if (k < size) laz[k] = MA::op(laz[k], a);
}
void push(int k) {
if (laz[k] == MA::unit()) return;
apply_at(2 * k, laz[k]), apply_at(2 * k + 1, laz[k]);
laz[k] = MA::unit();
}
};
#line 9 "main.cpp"
using Mono = Monoid_Max_Idx<ll>;
using P = pair<ll, int>;
/*
解説を読む
各点からパスを下るのは subtree の探索なので簡単
辺を上るところは heavy path のみ計算しておくとよい
heavy edge で v に来たときにどこまでくだるかを計算する
点更新をするとそれに関わる light edge は少ないのでできる
*/
void solve() {
LL(N, Q);
VEC(ll, A, N);
Graph<ll, 1> G(N);
FOR(v, 1, N) {
INT(p, x);
--p;
G.add(p, v, x);
}
G.build();
Tree<decltype(G)> tree(G);
vc<int> heavy_child(N, -1);
vc<pair<int, int>> light_range(N);
FOR(v, N) {
for (auto& e: G[v]) {
if (tree.head[e.to] == tree.head[v]) heavy_child[v] = e.to;
}
int L = tree.LID[v], R = tree.RID[v];
if (heavy_child[v] == -1) {
light_range[v] = {L + 1, R};
} else {
int c = heavy_child[v];
int Lc = tree.LID[c], Rc = tree.RID[c];
assert(Lc == L + 1);
light_range[v] = {Rc, R};
}
}
vi dep(N);
FOR(v, N) dep[v] = tree.dist_weighted(0, v);
/*
seg1[v] := dep[v]-A[v]
seg2[v] := -2dep[v]+dep[w]-A[w] (w notin heavy)
*/
using AM = ActedMonoid_MaxIdx_Add<ll>;
Lazy_SegTree<AM> seg1(N, [&](int i) -> P {
int v = tree.V[i];
return {dep[v] - A[v], v};
});
Lazy_SegTree<AM> seg2(N);
auto upd_seg2 = [&](int v) -> void {
ll av = dep[v] - seg1.prod(tree.LID[v], tree.LID[v] + 1).fi;
P p = {-2 * dep[v] + dep[v] - av, v};
auto [L, R] = light_range[v];
P q = seg1.prod(L, R);
q.fi -= 2 * dep[v];
seg2.set(tree.LID[v], Mono::op(p, q));
};
FOR(v, N) upd_seg2(v);
auto upd = [&](int v, ll add) -> void {
// subtree add
seg1.apply(tree.LID[v], tree.RID[v], -add);
seg2.apply(tree.LID[v], tree.RID[v], -add);
while (1) {
v = tree.head[v];
if (v == 0) break;
v = tree.parent[v];
upd_seg2(v);
}
};
auto solve = [&](int v) -> P {
int v0 = v;
ll av = dep[v] - seg1.prod(tree.LID[v], tree.LID[v] + 1).fi;
P p = {-av, v};
int l = tree.LID[v], r = tree.LID[v];
while (1) {
// [l,r) から来た
// ここから下る場合
int L = tree.LID[v], R = tree.RID[v];
assert(L <= l && r <= R);
for (auto& [a, b]: {pair<int, int>{L, l}, pair<int, int>{r, R}}) {
auto x = seg1.prod(a, b);
x.fi += dep[v0] - 2 * dep[v];
p = Mono::op(p, x);
}
// どこかまであがってから下る場合
if (v != tree.head[v]) {
int hv = tree.head[v];
auto x = seg2.prod(tree.LID[hv], tree.LID[v]);
x.fi += dep[v0];
p = Mono::op(p, x);
}
v = tree.head[v];
if (v == 0) break;
l = tree.LID[v], r = tree.RID[v];
v = tree.parent[v];
}
return p;
};
FOR(q, Q) {
LL(x, y, v);
--x, --y;
upd(y, v);
auto ans = solve(x);
print(ans.se + 1, ans.fi);
}
}
signed main() {
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3548kb
input:
6 6 1 1 4 5 1 4 1 5 2 0 3 2 4 1 5 6 3 2 -100000 1 2 100000 1 1 0 2 2 66 3 1 5 4 4 -3
output:
6 100005 6 10 6 10 1 4 1 -1 1 1
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
5 6 -10 0 2 -4 8 1 7 1 1 2 2 2 -2 1 1 100 2 1 -100 1 1 0 4 3 10 2 5 3 5 2 2
output:
4 -87 1 17 4 13 1 19 1 17 1 15
result:
ok 6 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
6 3 0 0 0 0 0 0 1 10 1 10 1 -100 4 10 4 11 1 1 0 4 1 0 1 4 1000
output:
2 10 6 11 2 10
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
2 0 1 1 1 3
output:
result:
ok 0 lines
Test #5:
score: 0
Accepted
time: 1014ms
memory: 47544kb
input:
200000 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
119017 15000000000 120167 17000000000 119017 15000000000 119017 15000000000 120167 17000000000 120167 15000000000 120167 16000000000 119017 17000000000 119017 16000000000 119017 12000000000 119017 17000000000 120167 16000000000 120167 14000000000 120167 17000000000 120167 18000000000 120167 16000000...
result:
ok 200000 lines
Test #6:
score: 0
Accepted
time: 1144ms
memory: 46408kb
input:
200000 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
169355 88000000000 171273 95000000000 171273 100000000000 169355 88000000000 169355 93000000000 169355 97000000000 169355 93000000000 171273 78000000000 171273 86000000000 169355 90000000000 169355 84000000000 169355 80000000000 169355 78000000000 171273 84000000000 169355 89000000000 171273 8400000...
result:
ok 200000 lines
Test #7:
score: 0
Accepted
time: 898ms
memory: 47320kb
input:
200000 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
60406 17000000000 163359 19000000000 163359 18000000000 163359 17000000000 163359 18000000000 60406 17000000000 163359 16000000000 60406 16000000000 60406 18000000000 163359 17000000000 163359 16000000000 163359 15000000000 163359 18000000000 163359 16000000000 60406 13000000000 163359 15000000000 6...
result:
ok 200000 lines
Test #8:
score: 0
Accepted
time: 1088ms
memory: 46492kb
input:
200000 200000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
158239 95000000000 170228 90000000000 170228 91000000000 158239 97000000000 158239 90000000000 170228 97000000000 170228 95000000000 158239 89000000000 170228 84000000000 158239 97000000000 158239 88000000000 170228 81000000000 158239 89000000000 170228 84000000000 170228 84000000000 158239 83000000...
result:
ok 200000 lines
Test #9:
score: 0
Accepted
time: 883ms
memory: 47952kb
input:
200000 200000 -999999197 -999999547 -999999355 -999999799 -999999360 -999999720 -999999365 -999999419 -999999958 -999999574 -999999169 -999999422 -999999695 -999999971 -999999820 -999999822 -999999107 -999999420 -999999519 -999999970 -999999601 -999999521 -999999134 -999999638 -999999338 -999999570 ...
output:
2841 999999254 109445 999999369 58340 999999315 117049 999999782 118472 999999076 24148 999999131 47844 999999290 113056 999999668 46680 999999228 109091 999999634 68365 999999666 156304 999999674 39689 999999729 103343 999999322 123506 999999661 189258 999999210 142816 999999890 88985 999999626 120...
result:
ok 200000 lines
Test #10:
score: 0
Accepted
time: 1026ms
memory: 46460kb
input:
200000 200000 -999999902 -999999301 -999999682 -999999655 -999999078 -999999674 -999999335 -999999307 -999999892 -999999582 -999999768 -999999854 -999999299 -999999298 -999999510 -999999440 -999999916 -999999930 -999999447 -999999825 -999999586 -999999447 -999999186 -999999634 -999999258 -999999756 ...
output:
43055 999999140 49534 999999915 34106 999999771 160878 999999227 148508 999999679 72994 999999134 163193 999999850 63938 999999143 54880 999999740 52045 999999113 26995 999999039 87143 999999281 74906 999999554 172131 999999137 138024 999999394 57682 999999637 62669 999999051 81932 999999518 33406 9...
result:
ok 200000 lines
Test #11:
score: 0
Accepted
time: 916ms
memory: 46508kb
input:
200000 200000 -999999602 -999999216 -999999710 -999999943 -999999715 -999999936 -999999594 -999999877 -999999394 -999999644 -999999110 -999999223 -999999342 -999999960 -999999730 -999999642 -999999058 -999999863 -999999406 -999999319 -999999812 -999999634 -999999519 -999999599 -999999799 -999999846 ...
output:
183067 999999909 99888 999999736 7724 999999364 161568 999999298 93017 999999903 105263 999999788 62219 999999053 132842 999999223 45435 999999362 159394 999999759 25951 999999780 118834 999999191 154586 999999744 82508 999999076 164452 999999372 100552 999999562 155126 999999332 100719 999999406 19...
result:
ok 200000 lines
Test #12:
score: 0
Accepted
time: 1069ms
memory: 47884kb
input:
200000 200000 -999999723 -999999956 -999999679 -999999610 -999999755 -999999845 -999999359 -999999914 -999999060 -999999981 -999999093 -999999136 -999999983 -999999772 -999999112 -999999777 -999999827 -999999612 -999999413 -999999471 -999999757 -999999293 -999999685 -999999999 -999999791 -999999170 ...
output:
99717 999999755 15526 999999972 23346 999999932 42421 999999452 2286 999999049 193610 999999232 70168 999999164 26214 999999570 138962 999999287 155319 999999407 47662 999999714 111146 999999883 120662 999999304 98100 999999670 27642 999999638 20252 999999486 87487 999999101 177165 999999970 195686 ...
result:
ok 200000 lines
Test #13:
score: 0
Accepted
time: 797ms
memory: 47372kb
input:
200000 200000 4 0 2 8 -2 -3 -10 7 -4 -8 -2 10 9 9 -9 -5 -7 -2 6 1 -9 -1 -5 0 2 0 9 1 -9 1 7 -1 -5 -8 -9 1 6 -1 7 -2 9 -10 9 -7 6 9 -3 -2 -4 0 -4 -2 10 -3 -8 2 -1 3 -8 -7 -4 5 -9 5 -7 8 -7 -8 -3 6 3 -8 1 -10 0 -3 3 7 10 4 4 -4 -6 -7 -5 -5 -4 6 -5 -7 -2 -5 9 0 8 10 7 -5 -7 -5 7 10 2 -7 -8 9 1 1 -6 8 -...
output:
189813 1486 189813 1227 31620 1530 31620 935 189813 917 189813 1403 189813 1394 31620 1303 189813 1096 189813 1287 189813 1298 189813 1322 189813 1167 31620 1527 189813 1337 31620 1313 189813 1393 189813 854 189813 1271 31620 1459 31620 806 189813 1076 189813 1148 189813 1300 189813 1282 189813 1265...
result:
ok 200000 lines
Test #14:
score: 0
Accepted
time: 761ms
memory: 48552kb
input:
200000 200000 0 -1 2 -8 0 3 0 7 2 10 5 7 1 2 -9 7 -2 -3 1 6 -8 -10 -6 8 -1 -4 -7 -9 10 -1 3 -6 -3 9 -8 6 10 7 7 3 -2 -2 -8 5 -9 -10 0 -7 -10 2 -6 2 -8 8 -6 -5 3 5 2 -2 7 -2 -8 -10 -3 4 0 8 -4 8 -10 10 -3 -5 2 3 4 2 -4 -2 7 10 -8 6 -7 -3 9 3 -10 0 -7 -5 10 -7 -10 -9 -7 -10 1 -2 -9 3 3 1 8 -6 1 3 -3 2...
output:
86396 1446 86396 1315 196929 1328 86396 1593 196929 1461 86396 1387 196929 1155 196929 1477 196929 1623 86396 1359 196929 1195 86396 1751 86396 1267 196929 1726 86396 1399 86396 1486 196929 1612 196929 1021 86396 1608 196929 1229 196929 1591 86396 1455 196929 1589 86396 1486 86396 948 86396 1810 196...
result:
ok 200000 lines
Test #15:
score: 0
Accepted
time: 809ms
memory: 47372kb
input:
200000 200000 -8 -9 5 -8 5 6 -3 -10 -8 3 9 1 10 8 -9 7 -4 0 -4 -6 -8 -10 7 4 4 9 2 7 7 -10 -9 -4 8 10 10 -10 9 -6 -2 -1 7 1 4 -1 6 6 -9 -8 9 10 -9 2 8 -8 0 1 7 -10 7 -8 -6 5 5 -8 10 5 7 3 7 10 10 7 -3 1 3 9 1 1 3 4 -10 7 3 -2 -2 7 -8 5 -7 2 5 7 -5 -10 1 2 -8 -10 1 6 8 -4 9 -8 0 -5 10 5 -9 0 9 0 0 7 ...
output:
81800 939 81800 883 81800 718 185970 99 81800 933 19381 1115 81800 868 81800 916 81800 915 81800 439 81800 807 19381 1045 81800 888 81800 871 81800 940 81800 709 81800 564 81800 800 81800 810 81800 533 19381 970 81800 690 81800 939 81800 592 81800 940 81800 925 81800 898 81800 763 185970 66 19381 86...
result:
ok 200000 lines
Test #16:
score: 0
Accepted
time: 797ms
memory: 48364kb
input:
200000 200000 5 3 5 -3 -6 -8 4 -2 2 -7 3 -1 2 6 -9 -2 5 7 9 7 2 -1 -6 -9 9 9 7 -10 9 1 8 -5 2 6 -1 9 -4 2 -10 4 0 -8 -5 -3 3 -3 -1 -9 3 -8 6 -6 -2 2 6 2 -7 -4 0 10 9 2 10 -6 -3 5 6 -2 6 0 -3 9 -7 7 -8 -9 -1 -4 2 -3 -3 -4 1 6 0 -4 5 -2 -5 9 -4 -1 -4 0 4 4 -8 10 9 2 -4 10 6 -4 3 5 -6 7 -2 -5 9 -2 7 9 ...
output:
37558 536 160880 496 160880 586 199237 483 160880 263 160880 642 37558 522 37558 569 37558 700 199237 453 160880 555 37558 781 37558 478 160880 641 160880 603 160880 476 160880 456 160880 539 160880 535 37558 562 199237 522 160880 552 160880 577 160880 391 199237 454 37558 658 160880 425 199237 499 ...
result:
ok 200000 lines
Test #17:
score: 0
Accepted
time: 809ms
memory: 47832kb
input:
200000 200000 5 -1 9 6 -4 -1 5 -2 9 -10 7 9 -1 -9 -9 10 7 7 4 -6 2 -9 6 -5 10 6 -9 10 6 -9 5 -7 1 2 1 10 -4 -7 -1 -3 2 -1 -1 -4 9 -9 6 7 9 3 8 7 -6 -4 -5 -4 10 2 2 -6 -9 8 -5 -4 1 5 9 -8 5 2 9 6 -10 5 -6 -7 4 -5 1 -9 9 -7 3 -2 -2 2 -3 0 -6 -1 8 -2 10 -7 8 -1 -1 5 5 -3 1 3 -10 -9 -2 7 2 -8 -7 -7 -1 -...
output:
1846 1057 1846 1191 1846 939 1846 1093 199836 1214 1846 878 199836 1140 199836 1114 199836 858 199836 1217 1846 872 199836 1043 199836 1001 199836 926 199836 854 199836 1183 1846 1476 199836 1155 199836 1135 199836 1396 199836 1118 1846 1241 1846 1361 199836 1128 1846 1131 199836 1129 1846 1256 1998...
result:
ok 200000 lines
Test #18:
score: 0
Accepted
time: 951ms
memory: 47716kb
input:
200000 200000 8 -2 10 -4 6 7 6 -4 5 -8 -5 6 2 -9 7 1 -6 -5 0 -9 3 0 1 5 -9 -1 -2 8 -8 8 -10 0 8 -5 9 4 -8 10 -4 8 -2 0 6 -7 -5 3 -4 7 1 5 3 10 -6 4 -3 -8 -7 -3 -7 -2 5 2 -1 8 7 0 -9 9 1 8 -1 3 -7 0 -8 6 -1 5 -7 -8 9 2 -1 8 -8 1 -7 10 -2 8 -8 -1 -5 -7 5 -10 1 -5 4 5 -5 4 -6 6 1 -5 9 9 6 5 1 1 -8 2 -8...
output:
183978 58 183978 65 51659 56 44937 101 183978 82 183978 66 183978 56 183978 72 51659 64 183978 59 183978 81 183978 56 183978 59 183978 61 183978 77 51659 45 183978 65 183978 60 183978 55 183978 97 183978 69 183978 65 183978 77 183978 67 183978 100 183978 78 183978 40 183978 61 51659 43 183978 91 183...
result:
ok 200000 lines
Test #19:
score: 0
Accepted
time: 972ms
memory: 46468kb
input:
200000 200000 -5 2 3 -8 5 0 -8 -8 -6 3 8 -5 -7 6 7 10 5 -4 5 -1 7 4 10 -3 -10 3 -3 -8 -5 -7 2 -3 -3 3 -1 -1 9 2 4 -6 9 -3 -10 -5 -2 5 10 -9 7 6 9 1 -9 7 -5 -5 10 -9 0 1 -10 5 -2 10 7 4 5 -6 10 6 -9 2 -3 -6 -1 0 10 6 -10 -10 9 -4 10 -1 -6 -1 5 -9 -4 1 -3 8 -2 0 2 9 -6 0 4 -7 7 -6 10 -6 5 -10 8 -10 3 ...
output:
146090 70 36198 50 36198 69 36198 71 188299 39 146090 78 36198 73 180467 62 36198 90 146090 97 36198 80 188299 67 188299 77 146090 64 36198 63 36198 69 36198 57 36198 62 36198 73 36198 46 36198 91 180467 50 36198 58 36198 99 146090 74 36198 84 36198 79 188299 71 188299 58 36198 80 36198 89 180467 53...
result:
ok 200000 lines
Test #20:
score: 0
Accepted
time: 1117ms
memory: 47212kb
input:
200000 200000 -7 -1 -6 0 6 -5 -8 10 -6 0 10 0 -1 7 -4 -10 -10 8 1 10 -1 -5 3 7 -4 3 -1 -1 1 -3 -3 0 -2 6 9 -6 -1 1 -8 -2 10 -1 5 -7 -2 4 -1 2 -7 7 4 -7 2 -1 -1 -6 -7 -4 -3 8 -9 -9 2 -2 -8 10 0 -8 -5 -8 6 6 9 -1 2 3 10 -8 6 -4 8 5 8 -3 -5 6 -7 -10 -8 -2 7 1 -10 -5 2 -4 4 -10 8 -10 -9 6 -4 -5 -10 -10 ...
output:
159245 116 159245 132 159245 129 131983 105 159245 112 170387 140 159245 202 119365 133 159245 153 159245 186 119365 134 159245 147 170387 140 159245 124 159245 110 170387 161 159245 136 159245 151 119365 115 159245 125 170387 55 159245 127 159245 99 170387 148 119365 182 159245 148 170387 147 15924...
result:
ok 200000 lines
Test #21:
score: 0
Accepted
time: 1102ms
memory: 46472kb
input:
200000 200000 10 -9 2 1 -5 -2 10 -7 4 -7 -8 -2 -9 0 -8 2 -8 7 -4 -6 -8 -9 -6 -6 1 3 4 -6 -1 9 -7 2 -8 -2 -2 3 2 8 0 -5 3 2 -8 -8 3 3 7 -3 -1 9 2 5 5 -8 1 -9 0 -6 -10 5 -1 -2 7 -1 -4 10 -10 8 -10 -6 -3 3 -4 4 4 5 7 -5 -8 -6 -2 -2 -7 9 -7 -5 6 9 -6 4 -2 10 -9 9 5 7 -10 6 -5 6 4 -4 1 3 -10 -8 7 3 0 2 2...
output:
166862 103 178216 106 166862 194 166862 146 166862 187 166862 155 166862 147 166862 168 161139 86 166862 152 166862 130 166862 138 161139 52 161139 134 166862 126 161139 147 161139 120 161139 130 166862 159 178216 148 166862 131 178216 103 166862 174 161139 118 161139 175 161139 110 178216 120 16686...
result:
ok 200000 lines
Test #22:
score: 0
Accepted
time: 797ms
memory: 47968kb
input:
200000 200000 -278 780 -568 -958 -717 530 65 -148 460 -357 214 797 -558 -641 -742 183 -838 762 14 -374 -657 285 -829 511 -33 247 284 752 316 709 342 162 -173 262 176 499 -253 982 894 -281 -687 -626 -201 -497 -258 -204 768 -314 -459 467 16 -188 -88 -787 -470 -615 -790 -108 519 708 914 370 -99 -642 80...
output:
6692 164001 198824 115354 6692 148012 198824 127788 198824 163309 198824 216866 6692 135112 198824 171084 6692 114621 6692 182111 198824 110560 198824 120897 6692 140267 6692 151894 198824 114449 6692 117661 198824 188763 198824 156260 6692 106214 6692 211792 198824 123137 198824 127957 198824 88170...
result:
ok 200000 lines
Test #23:
score: 0
Accepted
time: 794ms
memory: 48248kb
input:
200000 200000 -330 323 181 -256 477 -218 -344 -966 471 879 257 -788 388 876 -20 -102 -624 85 756 78 388 -878 335 -730 -647 476 -122 -560 -271 198 -50 -861 -602 562 231 157 450 -407 -290 377 -879 -301 831 857 -156 273 -262 106 697 436 -43 604 -109 -794 -859 930 844 294 -635 137 923 618 -851 -316 165 ...
output:
2074 54546 48050 82045 2074 84751 131596 22582 2074 28346 2074 19608 48050 80429 2074 50455 163113 19941 2074 62564 2074 27020 2074 79208 2074 52097 2074 71047 163113 27944 2074 51766 163113 27121 2074 77357 2074 70004 2074 64162 163113 25573 2074 70604 2074 21638 2074 78261 2074 28123 2074 61909 15...
result:
ok 200000 lines
Test #24:
score: 0
Accepted
time: 787ms
memory: 47972kb
input:
200000 200000 -382 980 -539 -668 201 -154 -168 -669 481 -773 -585 -371 -667 976 -997 729 -994 596 383 -283 -871 -853 310 917 -375 -483 -528 -455 -784 500 672 -466 -730 861 -16 -997 -35 -681 526 -383 117 -790 446 211 -356 -949 708 755 967 103 -175 -303 -661 -874 826 -412 -409 -190 -674 379 119 939 39...
output:
189649 59423 154927 83069 154927 79250 189649 45995 154927 88677 73010 24028 19643 20139 189649 81888 189649 35197 33111 39012 19643 19728 189649 51774 154927 68970 19643 29785 33111 26431 19643 10137 100901 17070 19643 40879 154927 67046 189649 55697 40018 25841 123161 39264 100901 21242 189649 320...
result:
ok 200000 lines
Test #25:
score: 0
Accepted
time: 828ms
memory: 47996kb
input:
200000 200000 -434 522 513 35 508 213 -806 -601 -394 -653 -240 932 581 -394 -275 444 -779 -80 -876 -946 403 -16 -830 -626 710 -555 -48 536 -485 -312 -909 -603 -274 274 924 -224 667 -69 -658 275 -962 -465 61 679 -255 944 -20 -597 122 71 579 -96 -983 -880 208 -867 339 -903 757 621 -986 72 -583 638 -19...
output:
175422 81241 175422 59816 175422 79939 175422 69444 120467 45194 175422 61982 175422 63786 120467 48547 175422 66847 175422 60683 175422 45243 120467 50666 175422 54414 175422 68413 175422 37109 175422 62968 175422 73082 175422 74096 175422 84271 120467 46787 175422 48766 175422 65938 175422 56732 1...
result:
ok 200000 lines
Test #26:
score: 0
Accepted
time: 793ms
memory: 48424kb
input:
200000 200000 629 -821 -739 -680 816 -535 484 -304 -384 583 -196 535 -473 -294 749 159 852 431 -134 -193 -554 -64 32 -981 982 -628 -453 110 -999 -10 -187 678 -704 574 -136 622 -631 -645 158 402 -852 -954 -908 33 -455 -278 950 -177 694 624 -669 696 -118 -960 705 678 -330 -501 -397 51 -91 -493 666 77 ...
output:
56714 67790 134738 49293 79978 35924 56714 55691 134738 57980 134738 28404 134738 37729 134738 62511 134738 61821 134738 43503 56714 62183 134738 43273 134738 38273 134738 47646 56714 44972 134738 44260 56714 43580 134738 52877 56714 43631 134738 60410 56714 29951 56714 50659 134738 41540 56714 5045...
result:
ok 200000 lines
Test #27:
score: 0
Accepted
time: 863ms
memory: 46876kb
input:
200000 200000 -292 95 205 513 -100 -988 387 -774 -634 320 564 69 -822 225 662 -498 -945 -988 969 955 737 -78 165 -847 -371 207 -559 76 257 997 -120 946 639 -233 762 -968 18 -817 -765 -225 -921 801 724 671 -228 626 -341 -601 -574 641 366 742 -774 272 835 836 -244 514 -21 463 -787 -358 451 527 -730 -5...
output:
182218 4742 191865 3743 175383 3625 175383 6667 191865 7265 191865 8869 175383 5423 191865 6594 175383 4933 191865 6165 85072 6874 175383 2562 182218 6150 182218 6605 191865 4409 175383 4478 182218 5443 191865 6306 128605 4745 191865 6409 175383 6581 175383 8072 191865 7073 182218 7376 142673 4898 1...
result:
ok 200000 lines
Test #28:
score: 0
Accepted
time: 929ms
memory: 47820kb
input:
200000 200000 646 -563 -847 926 707 647 -977 -842 -61 -915 218 767 -882 -407 -946 -213 -274 -83 -659 202 -6 784 -696 -493 -643 -22 -153 274 -928 695 -842 -32 766 -533 -179 -928 201 572 419 535 -728 477 -6 -683 -330 -152 -426 -135 271 974 -388 -351 -754 -836 -548 176 123 414 247 -665 318 -377 -569 -9...
output:
169370 6892 92053 6172 92053 5500 169370 7744 169370 7519 169370 9066 169370 6762 169370 3723 169370 8889 92053 6099 169370 8372 92053 6487 169370 6899 92053 4259 92053 9598 92053 9325 169370 8841 92053 6648 169370 5170 169370 6221 92053 7741 169370 7643 169370 5535 169370 6428 169370 7574 169370 65...
result:
ok 200000 lines
Test #29:
score: 0
Accepted
time: 1080ms
memory: 46540kb
input:
200000 200000 79 -980 791 472 -953 460 -681 142 -788 -919 -886 -488 -95 -412 -344 583 -724 -40 31 -569 902 -781 897 200 611 192 -529 500 -376 387 222 977 550 -130 -826 358 446 -975 -148 980 608 -561 -718 -856 -996 -278 -688 282 552 21 833 156 -928 -826 256 -77 -187 726 650 387 85 193 -811 -250 782 -...
output:
169911 14238 129848 12265 129848 12534 129848 3390 129848 12768 129848 10948 129848 17352 129848 12092 129848 12207 129848 12389 129848 13189 129848 9052 129848 13160 129848 11996 129848 8471 129848 17853 129848 11831 129848 16267 129848 12954 129848 16415 129848 9836 129848 16149 129848 14824 12984...
result:
ok 200000 lines
Test #30:
score: 0
Accepted
time: 1078ms
memory: 48128kb
input:
200000 200000 27 -323 -158 -242 469 -288 912 -676 338 -799 -842 815 -848 -312 -435 -817 -208 -717 471 -930 -54 -830 -243 960 -889 119 -934 -510 -962 690 -171 -46 422 170 -1000 903 33 752 669 523 -168 650 12 -689 805 501 585 931 -877 -10 472 947 -63 282 -362 -532 560 -873 -806 932 980 -371 -677 -508 ...
output:
141932 15629 141932 13715 157261 19961 157261 16314 157261 20730 141932 15089 141932 20808 141932 16060 157261 25588 141932 23683 157261 23091 141932 12174 141932 17111 141932 16198 141932 23792 157261 20595 141932 23125 141932 21082 141932 22359 141932 19804 141932 16386 141932 16760 141932 17383 1...
result:
ok 200000 lines
Test #31:
score: 0
Accepted
time: 737ms
memory: 48544kb
input:
200000 200000 -78938 -237 -83708 56279 10781 33254 69630 595 -84581 62048 47188 26859 72774 38375 6196 83136 -60621 -72415 -9837 89921 -74503 -52140 -60706 5786 30282 -16095 -81452 36083 -6890 -57719 22119 31918 -88256 -44212 -68778 19932 -1293 5899 30311 22182 -46523 24090 67711 -57113 27539 9321 -...
output:
195871 4674003 5331 4182008 77371 9272375 77371 8914088 195871 3749265 195871 5991826 77371 5325662 195871 5432488 195871 7297339 195871 8819768 195871 5133841 77371 5689322 195871 6307953 5331 4188768 195871 6562566 195871 6846876 195871 6142388 77371 5229418 195871 7756169 195871 3932427 195871 53...
result:
ok 200000 lines
Test #32:
score: 0
Accepted
time: 734ms
memory: 48300kb
input:
200000 200000 63431 22480 36051 -87639 -74512 13654 10158 18608 -29864 45667 6479 -76995 -92552 32239 13823 -7509 -7195 -35282 -46996 76110 -80805 82947 3050 25735 -77144 97232 -35393 -45624 96662 -68312 -96615 54409 19102 76243 -55719 65777 89528 49777 -57199 -73564 40699 -99001 -11804 -70949 71685...
output:
105078 9906330 105078 7961207 12374 7351312 12374 5630010 12374 4641841 12374 5100129 105078 10013028 195542 5048396 12374 10193765 12374 7173676 12374 7296640 12374 7906794 12374 9745059 12374 6360148 12374 4627493 12374 9806016 12374 7014815 12374 9005188 105078 9811361 12374 6794648 12374 7945428...
result:
ok 200000 lines
Test #33:
score: 0
Accepted
time: 736ms
memory: 47908kb
input:
200000 200000 97442 99376 -44191 85405 65515 -31265 -23996 90800 -29325 83465 57412 98648 -3697 54963 87775 -72836 20912 30713 -29976 -58204 -32929 43351 66807 -33813 -38748 -55768 64845 -73152 25531 -78905 -40665 -43605 5955 -3302 -42659 28581 -48512 -52167 1112 97015 -43219 32087 -8279 61038 -8417...
output:
111941 5786320 111941 6942306 180489 4715898 111941 5881215 111941 6198052 60026 4378894 180489 4587714 180489 6080351 180489 5713673 180489 6675874 60026 5326668 111941 6856737 111941 6704165 180489 6749516 180489 8161056 6831 3301654 111941 5398770 28619 5522688 180489 7203935 180489 7262298 11194...
result:
ok 200000 lines
Test #34:
score: 0
Accepted
time: 817ms
memory: 48332kb
input:
200000 200000 39810 -23728 -44937 87308 -73957 -76183 -29288 54634 -28787 12905 16703 20112 30978 48826 95402 36520 -96802 -77976 -12956 -46696 -13913 3754 -94756 -39181 -352 82876 -89096 70460 74905 -35318 94781 -75294 -7192 -28669 87362 20246 -11869 45890 59424 1269 -10177 -62143 -33615 -6977 -653...
output:
44800 10553419 199177 14349643 199177 13456087 199177 11021917 199177 14756966 44800 15861070 199177 16152683 199177 14301447 199177 15710649 199177 13456793 199177 15487322 199177 16590358 199177 15104868 199177 12689724 199177 12923720 44800 11423166 199177 14079585 199177 17069656 199177 15381092...
result:
ok 200000 lines
Test #35:
score: 0
Accepted
time: 773ms
memory: 48720kb
input:
200000 200000 -72001 53168 74822 -56610 66070 -95783 82380 -73175 25931 -3475 -78186 -4245 65653 -74272 -30647 -54125 -43377 -66161 -50115 -6327 -20216 -61160 -31000 -44550 92223 -3799 11142 -65426 57953 8268 96551 -27485 -99836 91786 -99579 91408 78953 89768 -82265 51345 51727 14766 -4772 -20813 -2...
output:
126858 6222402 30198 5730776 158825 5475444 83003 3028534 30198 5407055 30198 6324753 83003 3186913 83003 1393565 83003 5263551 126858 6214486 126858 6682491 158825 4538919 83003 7600797 30198 5992208 83003 7622403 158825 4827013 30198 5935643 30198 6761611 126858 4919850 83003 6797860 126858 499460...
result:
ok 200000 lines
Test #36:
score: 0
Accepted
time: 871ms
memory: 46652kb
input:
200000 200000 -57035 27453 55255 48995 66645 4314 6118 96714 29694 -42486 82309 -14739 10017 -36199 -1103 -89759 -98077 29916 56723 -28536 3081 82777 24566 9253 68169 -94401 58660 -536 -61324 78429 -83916 -85356 35471 12631 -56904 33789 13193 -66721 68812 -59323 61604 -82476 75957 -12013 -80138 -183...
output:
149879 469830 167101 559400 149879 577390 149879 547189 149879 655525 149879 620137 167101 575983 149879 558341 149879 618397 149879 694811 103479 634825 149879 626267 149879 520096 149879 729919 149879 417627 149879 523375 149879 620373 149879 581878 54998 664705 167101 660358 103479 759142 103479 ...
result:
ok 200000 lines
Test #37:
score: 0
Accepted
time: 924ms
memory: 47412kb
input:
200000 200000 54776 -49443 56000 47092 -19202 49232 40271 24522 -25023 -26106 -76983 63798 -78838 -4744 45449 886 73817 -61397 93882 -94223 9383 -77628 -39191 14621 29773 -7727 -41579 55853 89304 89022 60136 -78986 48618 92177 -69964 96303 -77629 35223 64680 61741 -25617 11754 47114 -23496 75717 -76...
output:
47220 399311 47220 597079 47220 367065 116904 472243 47220 411168 141186 476507 47220 333175 141186 512389 141186 621730 198140 457951 60644 673231 163549 564404 116904 549739 47220 786060 47220 498504 47220 506635 47220 436303 141186 743344 47220 405295 60644 589425 141186 434615 116904 549802 4722...
result:
ok 200000 lines
Test #38:
score: 0
Accepted
time: 1093ms
memory: 47316kb
input:
200000 200000 -30490 -71150 -26823 -5091 12153 -90243 -56541 38617 -20822 -57273 -77363 57024 36663 -85214 68158 -51751 -35926 -40109 -89910 -9798 9819 53076 -64443 -25435 -73400 66914 85529 -58487 -91023 -73919 -67493 -87080 -96846 63548 -11770 -4679 25444 -55613 51418 30332 89124 56518 -22229 -440...
output:
195014 1269253 195014 1200499 195014 977717 195014 1600941 195014 976319 195014 1412188 195014 1356214 195014 1888844 195014 1111491 195014 1321147 195014 1199277 195014 1288979 195014 1557980 195014 1052709 195014 1688207 195014 1234110 195014 1533494 195014 1225325 195014 1299602 195014 1256341 19...
result:
ok 200000 lines
Test #39:
score: 0
Accepted
time: 1131ms
memory: 47744kb
input:
200000 200000 -88122 5746 92936 50992 -18961 10661 29809 -89192 33896 -19475 81928 32667 46020 -91351 21606 82923 17499 -28294 -72890 -23609 3516 13480 -687 -30804 -35004 59736 -14234 5628 -41649 -30333 -40404 -93450 90008 -15998 1290 -41875 -83735 -11735 -90272 80408 30524 -12395 -72883 -47097 -290...
output:
123715 1661978 123715 1284612 123715 1410945 186880 1201747 186880 1309577 186880 1309606 123715 885675 123715 1347640 123715 1708959 123715 1819244 186880 1164487 123715 1315656 123715 1662800 186880 1051766 123715 1761914 186880 1599154 123715 1952016 123715 1412998 123715 1448539 123715 1543943 1...
result:
ok 200000 lines
Test #40:
score: 0
Accepted
time: 732ms
memory: 48212kb
input:
200000 200000 -2133808 -3847354 -6578631 3728460 -1249104 -5887852 8966709 -7103961 1038053 -9013557 -8358424 -6980724 -4246803 1328505 2504079 -7981624 5114267 95658 -5945576 3768248 5131548 6120503 -6146410 -8001474 -8645948 3830861 4843965 5357277 -6436904 -4173505 3249193 -9418309 596999 2333101...
output:
64215 578879982 166201 459672444 166201 598936371 166201 533725903 166201 472587310 166201 629250950 64215 439071492 166201 528148605 64215 583397719 166201 560647048 64215 556453319 166201 618134269 166201 474098084 166201 537494262 166201 443204767 166201 536135448 64215 452182648 64215 172306967 ...
result:
ok 200000 lines
Test #41:
score: 0
Accepted
time: 793ms
memory: 48064kb
input:
200000 200000 -5362541 -1750198 1874401 3752656 -6195812 3591967 8421143 -471384 7152129 -8416092 -4873618 1861264 -9690679 3792294 -5573319 5372162 -6255123 2053504 -3919396 -31445 -9848592 1737340 6874489 -4354228 4199799 -5707746 -6361331 -7696811 -6029893 -2982958 -7360103 7573801 -9036274 36529...
output:
113109 800665526 113109 532799047 53437 838296198 113109 614467614 113109 811633883 113109 722522967 113109 964471552 113109 721808478 53437 696039806 53437 539884641 53437 645323366 53437 913177145 113109 548953763 53437 956464836 53437 574510753 113109 522500145 53437 533887869 113109 519601534 53...
result:
ok 200000 lines
Test #42:
score: 0
Accepted
time: 764ms
memory: 48940kb
input:
200000 200000 -8591274 6543983 -5803753 8809772 2660456 -5764110 -3354365 9898332 -1700876 -2785709 8545352 4506229 -5068717 7420189 2612145 3758867 2375487 5175455 -1893215 -3831138 -5992835 -8842846 -8874672 -1871086 -2954455 -279271 7466292 -1915004 -4458777 9437532 -6739456 3401805 7527478 -9994...
output:
45089 677498233 192528 587265966 86025 360044584 86025 561529564 192528 323071982 192528 498923045 45089 645686881 45089 433908789 45089 656741757 192528 378575850 45089 639712539 86025 708169674 45089 634326960 45089 682701845 139341 275373326 192528 538737599 86025 424183104 187995 248827022 13934...
result:
ok 200000 lines
Test #43:
score: 0
Accepted
time: 762ms
memory: 48328kb
input:
200000 200000 -6787088 8641139 2649280 8833968 -8483276 9912732 -8932850 -8502011 9446119 -7221164 6997240 7151194 -5479674 9883978 -5465253 -9084372 4809074 7133301 -4899954 -6466727 -972974 5609888 -5787937 1776160 9891292 -3620854 1293914 5030909 5882398 -4339003 8848273 -4639004 2927125 -8674316...
output:
107681 528372236 4492 449788266 4492 764598777 107681 481662749 107681 433423607 107681 446206026 159698 367812440 4492 538706582 4492 470666163 139106 178706677 107681 771698978 4492 544784582 175551 199900103 107681 363532421 107681 690528618 107681 694137358 4492 351928140 190513 407461604 107681...
result:
ok 200000 lines
Test #44:
score: 0
Accepted
time: 787ms
memory: 49044kb
input:
200000 200000 9984180 -9261705 4905288 8858165 6570016 -5640369 5488666 -1869434 -4439806 -6623700 -9517955 4763239 -5890630 -6488129 2720211 4269414 -1527398 -9744749 -2873774 4700662 4046888 -3806193 -7734120 -9543676 7769957 1807622 -4878464 6943903 1256490 1884464 -6793942 6156082 -6706148 -2321...
output:
36254 968989012 36254 1080534020 36254 1161249787 36254 737666719 36254 783307023 36254 747165123 36254 1081221117 36254 1057382846 36254 1043500132 36254 1187656833 36254 692552802 36254 995613563 36254 803471651 36254 775192624 36254 924412603 36254 911787647 36254 895154705 36254 901852843 36254 ...
result:
ok 200000 lines
Test #45:
score: 0
Accepted
time: 886ms
memory: 47448kb
input:
200000 200000 8219394 -1713779 -4203785 1401175 -9617073 -2537925 -8110871 3358289 -7829797 -5871334 9384112 3016477 6322975 -5833262 1644640 4226588 5677645 -2819871 4830461 7560479 4225591 1796178 4290195 -8421402 9314902 -6844913 5158408 -1799092 -4377564 -7952654 7573376 -6314820 -9456540 810912...
output:
199289 38564625 165645 62260574 199479 50636428 199289 52548704 165645 39839212 165645 54598571 165645 64629185 165645 74789378 199479 65447047 199289 54495441 199289 50995083 165645 69726304 165645 51863658 165645 62306945 199289 76426857 165645 56959124 165645 52504062 199289 61577724 199289 52522...
result:
ok 200000 lines
Test #46:
score: 0
Accepted
time: 993ms
memory: 47612kb
input:
200000 200000 6415208 -8843855 7343183 1376979 -4670365 7982257 2500533 1758631 1023208 -6468798 -9067776 371512 1701013 -8297051 9722038 -9127198 -7985885 -4777717 2804281 5163149 -5827190 -7623637 6236379 2898434 -3530845 7726612 -8669215 -2547981 248343 5823880 -8014353 2890095 -4856186 6789235 -...
output:
66568 64226255 66568 92191920 66568 99756028 66568 87598877 66568 86795331 66568 107068582 66568 73018576 66568 59436225 66568 64039949 66568 93515385 66568 70286009 66568 68574484 66568 65915947 66568 71477723 58119 77457566 66568 68807645 58119 61607144 66568 70577705 66568 69506160 66568 83100764...
result:
ok 200000 lines
Test #47:
score: 0
Accepted
time: 1149ms
memory: 47920kb
input:
200000 200000 2119983 2560046 4906325 -6985322 -8815028 -6989814 6183966 -4310 -930519 9811121 -611618 5904497 2007116 5261575 -5914919 2925251 -7855536 -6743685 -9538510 -4034848 181690 -7634422 336759 -2592869 -8446302 -8648606 -4995855 -2239171 8509220 -5267511 -6591028 -3064338 3146475 4216172 -...
output:
85515 100522874 85515 126544992 85515 80485907 184228 117425182 85515 175161942 85515 106265017 85515 180847764 85515 87787403 85515 128612401 85515 202957460 85515 145713535 85515 126838823 184228 122100756 85515 203010648 85515 141723991 85515 133891366 85515 158771055 85515 131355750 85515 178142...
result:
ok 200000 lines
Test #48:
score: 0
Accepted
time: 1175ms
memory: 47012kb
input:
200000 200000 -1108750 -375717 7162333 -1928206 6238265 -2542914 -5591542 -4601676 5183557 -9591416 -2159730 -220596 1596159 8889469 6007684 -3720964 -9159089 -4785839 -7512330 7132541 5201551 1785393 4587600 6087296 4399445 -3220131 3798850 9739661 5047418 955955 -2233242 -6072229 -1453879 5536060 ...
output:
189856 147273411 189856 91714211 146302 105137385 198383 132509513 178571 101087426 145513 73538331 145513 99348293 103536 144989198 178571 91804152 145513 102345018 136587 85110628 136587 123597381 146302 151194625 174764 198115698 178571 162475443 174764 129970491 174764 171878851 178571 174928907...
result:
ok 200000 lines
Test #49:
score: 0
Accepted
time: 742ms
memory: 48420kb
input:
200000 200000 73513521 -242563804 129333207 -100857506 10422640 880538576 799210907 476823238 -442306791 250812685 -103895571 945559944 -220719517 32113178 -117843565 337479566 430804773 -485176196 411375726 328308964 -706881720 117173126 -420122526 -909340072 -668214750 167652242 -260758322 -986520...
output:
125063 111245159008 2547 93696781284 2547 148185468006 2547 144465824169 125063 106167401076 2547 132056167881 2547 133437746608 2547 127857606641 2547 119594656067 125063 121941562046 2547 126538114390 2547 140323725698 2547 121821039032 2547 124764344150 2547 132035868206 125063 141206903768 2547 ...
result:
ok 200000 lines
Test #50:
score: 0
Accepted
time: 764ms
memory: 47980kb
input:
200000 200000 -453848883 355960354 741460388 382658783 697067048 916529258 585229289 -682375922 92279180 513899799 -571025896 715330590 -897868798 580483389 -177428812 -479513503 -874350863 970902914 134492395 -313217889 76161522 498780991 -711585495 -899087471 721037116 140946408 539910517 -3371977...
output:
66044 26632791182 6028 21543259105 48258 28700458026 144181 36933885610 122197 28206891504 75684 19126971966 144181 20007175038 105975 41623340175 16700 24255983079 171568 40169842621 48258 25489673289 66044 27450474995 171568 38470359601 105975 27914072397 191975 17501188823 103 13449370194 171568 ...
result:
ok 200000 lines
Test #51:
score: 0
Accepted
time: 797ms
memory: 47772kb
input:
200000 200000 428854126 -993637987 -889502225 -300800548 -373198752 -995602558 128157880 748359507 331897856 776986913 371909193 485101236 719949217 -923023903 109830737 408526135 63583293 965039109 -142390936 212230878 859204765 828511354 -708081169 -350777784 405256275 357330366 -954387938 6589697...
output:
118526 19993084686 91370 44038144470 91370 53573105148 91370 43303045772 91370 30789214319 91370 57634798224 91370 62497798520 23610 41792266316 23610 38530338560 146090 53857260132 146090 45839629362 91370 51397021298 11222 45384045478 91370 71161867290 146090 32789309127 91370 36247463937 146090 4...
result:
ok 200000 lines
Test #52:
score: 0
Accepted
time: 816ms
memory: 49360kb
input:
200000 200000 -688442866 -638203620 -867309632 425805533 608412950 -959611875 -85823738 -115872359 866483827 -959925974 -390188426 792928967 337767230 -669620986 50245490 -408466934 -946605049 421118218 -419274267 -672385767 -600841786 620184630 -756454346 -97435391 89475434 625591827 -448686393 -39...
output:
32568 15937305567 77140 33330353332 198320 24102357671 153098 12852078521 4144 20176739146 99781 36202627224 91366 12913045662 122454 14689898069 29582 13275161900 105830 11017808182 23220 16719320375 32568 22893310372 122454 23084123692 32568 26047093362 84789 13849669800 116500 11696685967 198320 ...
result:
ok 200000 lines
Test #53:
score: 0
Accepted
time: 801ms
memory: 47996kb
input:
200000 200000 489227437 -282769254 -255182451 -552621092 -704942642 -628653898 -542895148 724928482 -598930204 -696838859 552746663 562699613 -96292259 -173128277 580594831 531450206 286296401 710221708 -401190304 686087381 -112765837 706825201 952082686 450874297 -521272701 893853287 351982446 2525...
output:
198855 56135705842 66835 52056617029 50855 23799232594 198855 59521039332 66835 69889478192 66835 58208890786 107270 24508081359 198855 46323497546 198855 57780038186 50855 27359429352 198855 42496448498 198855 30442666640 66835 69750851624 66835 51181459668 198855 31689319794 90780 27722247458 1072...
result:
ok 200000 lines
Test #54:
score: 0
Accepted
time: 961ms
memory: 47336kb
input:
200000 200000 -905391558 -296321023 -895095180 -330571592 488559142 820071868 77958242 -76264839 -505681179 -187421993 612062922 995705206 968597457 -540040910 353449408 798664962 686228305 -310837715 -739760734 602933806 -20259235 -631275086 -614159622 -814138643 -825233362 -967053471 -199833674 18...
output:
125118 6352458389 130849 6747045239 130849 5717405437 125118 7273366894 125118 5144583494 130849 7413467989 125118 5533238050 130849 7102984283 130849 6791065215 130849 6556819070 130849 10594882281 125118 8136614877 130849 8177019988 130849 6453569315 125118 6772988648 125118 6165171548 125118 6936...
result:
ok 200000 lines
Test #55:
score: 0
Accepted
time: 988ms
memory: 47128kb
input:
200000 200000 -378029154 -651755389 492777641 942822327 -198085267 784081185 -3027435 787967027 959732851 -745476402 -625839461 687877474 -354253263 963466382 118067361 -141252178 -251705851 233083176 -757844697 -512449550 -803302477 -717915657 -322696653 932518965 -214485227 764685070 999497488 -76...
output:
76950 4790078581 76950 7153882698 116630 7343162848 116630 8888619853 116630 4179732297 103985 4795053079 76950 6572564239 103985 7613663799 103985 6017532379 86912 5589565954 76950 3678103161 116630 5731444971 76950 6960632720 76950 7223755771 76950 10256659845 76950 11309759975 103985 10994900946 ...
result:
ok 200000 lines
Test #56:
score: 0
Accepted
time: 1184ms
memory: 48192kb
input:
200000 200000 -933342177 531492564 -169102184 -573774070 -940071397 -388099888 -853012888 311124428 -26963932 -18016021 -954672244 -731593479 -201371793 -717885701 -663459763 228308833 -749419397 -605795503 -155583242 378346698 237252805 547211153 -395326329 -277692420 -263745375 -737918877 -5103639...
output:
176813 16584275296 176813 16391108588 176813 13876491482 176813 12663531724 176813 14733315476 176813 11278172863 176813 14902610763 176813 15020767787 176813 12895089387 176813 12673608958 176813 12897718541 176813 15244124748 96735 13791055452 176813 14984606749 176813 16048409303 176813 136691009...
result:
ok 200000 lines
Test #57:
score: 0
Accepted
time: 1153ms
memory: 46716kb
input:
200000 200000 -50639168 -869983279 443024996 152832011 -253426989 -352109205 -772027211 -848074732 507622039 540038387 283230138 -666855539 -583553780 -221392992 -428077716 -588684236 240392261 -906626602 -137499278 -263180155 777206255 633851723 -391822004 270617267 -579526216 -764624711 290304862 ...
output:
152610 12290940253 189175 10752740026 152610 11421072981 152610 12888353191 152610 12590702443 189175 12481775956 189175 10580911981 152610 15459955526 189175 11384523051 189175 15112464701 152610 14707468379 189175 12267327813 152610 12595181951 152610 11510600736 189175 12806305518 189175 11900099...
result:
ok 200000 lines