QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#188644 | #4918. 染色 | hos_lyric# | 25 | 339ms | 63332kb | C++14 | 13.7kb | 2023-09-26 08:19:13 | 2024-07-04 02:09:35 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
// T: monoid representing information of an interval.
// T() should return the identity.
// T(S s) should represent a single element of the array.
// T::push(T &l, T &r) should push the lazy update.
// T::pull(const T &l, const T &r) should pull two intervals.
template <class T> struct SegmentTreeRange {
int logN, n;
vector<T> ts;
SegmentTreeRange() : logN(0), n(0) {}
explicit SegmentTreeRange(int n_) {
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
}
template <class S> explicit SegmentTreeRange(const vector<S> &ss) {
const int n_ = ss.size();
for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
ts.resize(n << 1);
for (int i = 0; i < n_; ++i) at(i) = T(ss[i]);
build();
}
T &at(int i) {
return ts[n + i];
}
void build() {
for (int u = n; --u; ) pull(u);
}
inline void push(int u) {
ts[u].push(ts[u << 1], ts[u << 1 | 1]);
}
inline void pull(int u) {
ts[u].pull(ts[u << 1], ts[u << 1 | 1]);
}
// Applies T::f(args...) to [a, b).
template <class F, class... Args>
void ch(int a, int b, F f, Args &&... args) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return;
a += n; b += n;
for (int h = logN; h; --h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) push(aa);
} else {
if ((aa << h) != a) push(aa);
if ((bb << h) != b) push(bb);
}
}
for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
if (aa & 1) (ts[aa++].*f)(args...);
if (bb & 1) (ts[--bb].*f)(args...);
}
for (int h = 1; h <= logN; ++h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) pull(aa);
} else {
if ((aa << h) != a) pull(aa);
if ((bb << h) != b) pull(bb);
}
}
}
// Calculates the product for [a, b).
T get(int a, int b) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return T();
a += n; b += n;
for (int h = logN; h; --h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) push(aa);
} else {
if ((aa << h) != a) push(aa);
if ((bb << h) != b) push(bb);
}
}
T prodL, prodR, t;
for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
if (aa & 1) { t.pull(prodL, ts[aa++]); prodL = t; }
if (bb & 1) { t.pull(ts[--bb], prodR); prodR = t; }
}
t.pull(prodL, prodR);
return t;
}
// Calculates T::f(args...) of a monoid type for [a, b).
// op(-, -) should calculate the product.
// e() should return the identity.
template <class Op, class E, class F, class... Args>
#if __cplusplus >= 201402L
auto
#else
decltype((std::declval<T>().*F())())
#endif
get(int a, int b, Op op, E e, F f, Args &&... args) {
assert(0 <= a); assert(a <= b); assert(b <= n);
if (a == b) return e();
a += n; b += n;
for (int h = logN; h; --h) {
const int aa = a >> h, bb = b >> h;
if (aa == bb) {
if ((aa << h) != a || (bb << h) != b) push(aa);
} else {
if ((aa << h) != a) push(aa);
if ((bb << h) != b) push(bb);
}
}
auto prodL = e(), prodR = e();
for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
if (aa & 1) prodL = op(prodL, (ts[aa++].*f)(args...));
if (bb & 1) prodR = op((ts[--bb].*f)(args...), prodR);
}
return op(prodL, prodR);
}
// Find min b s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from left to right.
// Returns n + 1 if there is no such b.
template <class F, class... Args>
int findRight(int a, F f, Args &&... args) {
assert(0 <= a); assert(a <= n);
if ((T().*f)(args...)) return a;
if (a == n) return n + 1;
a += n;
for (int h = logN; h; --h) push(a >> h);
for (; ; a >>= 1) if (a & 1) {
if ((ts[a].*f)(args...)) {
for (; a < n; ) {
push(a);
if (!(ts[a <<= 1].*f)(args...)) ++a;
}
return a - n + 1;
}
++a;
if (!(a & (a - 1))) return n + 1;
}
}
// Find max a s.t. T::f(args...) returns true,
// when called for the partition of [a, b) from right to left.
// Returns -1 if there is no such a.
template <class F, class... Args>
int findLeft(int b, F f, Args &&... args) {
assert(0 <= b); assert(b <= n);
if ((T().*f)(args...)) return b;
if (b == 0) return -1;
b += n;
for (int h = logN; h; --h) push((b - 1) >> h);
for (; ; b >>= 1) if ((b & 1) || b == 2) {
if ((ts[b - 1].*f)(args...)) {
for (; b <= n; ) {
push(b - 1);
if (!(ts[(b <<= 1) - 1].*f)(args...)) --b;
}
return b - n - 1;
}
--b;
if (!(b & (b - 1))) return -1;
}
}
};
////////////////////////////////////////////////////////////////////////////////
template <class T> void bAdd(vector<T> &bit, int pos, const T &val) {
const int bitN = bit.size();
for (int x = pos; x < bitN; x |= x + 1) bit[x] += val;
}
template <class T> T bSum(const vector<T> &bit, int pos) {
T ret = 0;
for (int x = pos; x > 0; x &= x - 1) ret += bit[x - 1];
return ret;
}
template <class T> T bSum(const vector<T> &bit, int pos0, int pos1) {
return bSum(bit, pos1) - bSum(bit, pos0);
}
using U = unsigned long long;
int N, M, Q;
vector<int> O, L, R, X;
vector<U> V;
namespace brute {
vector<U> run() {
vector<set<int>> on(N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= M; ++j) {
on[i].insert(j);
}
}
vector<U> ws(N, 0);
vector<U> ans(Q, 0);
for (int q = 0; q < Q; ++q) {
if (O[q] == 1) {
for (int i = L[q]; i < R[q]; ++i) on[i].erase(X[q]);
} else if (O[q] == 2) {
for (int i = L[q]; i < R[q]; ++i) on[i].insert(X[q]);
} else if (O[q] == 3) {
int mn = M + 1;
for (int i = L[q]; i < R[q]; ++i) chmin(mn, *on[i].begin());
for (int i = L[q]; i < R[q]; ++i) if (mn == *on[i].begin()) ws[i] += V[q];
} else {
for (int i = L[q]; i < R[q]; ++i) ans[q] += ws[i];
}
// for(int i=0;i<N;++i){cerr<<i<<": ";pv(on[i].begin(),on[i].end());}
}
return ans;
}
} // brute
namespace sub2 {
// s -> xs[s], adding vs[s]
struct Func {
int as[2];
U vs[2];
Func() : as{0, 1}, vs{} {}
// *this then f
void mul(const Func &f) {
Func g;
for (int x = 0; x < 2; ++x) g.as[x] = f.as[as[x]];
for (int x = 0; x < 2; ++x) g.vs[x] = vs[x] + f.vs[as[x]];
*this = g;
}
};
struct Node {
int cnts[2];
U sum;
Func lz;
Node() : cnts{}, sum(0), lz() {}
Node(int x) : cnts{}, sum(0), lz() {
cnts[x] = 1;
}
void push(Node &l, Node &r) {
l.apply(lz);
r.apply(lz);
lz = Func();
}
void pull(const Node &l, const Node &r) {
for (int x = 0; x < 2; ++x) cnts[x] = l.cnts[x] + r.cnts[x];
sum = l.sum + r.sum;
}
void apply(const Func &f) {
for (int x = 0; x < 2; ++x) sum += cnts[x] * f.vs[x];
int tmp[2] = {};
for (int x = 0; x < 2; ++x) tmp[f.as[x]] += cnts[x];
memcpy(cnts, tmp, sizeof(tmp));
lz.mul(f);
}
};
vector<U> run() {
cerr<<"[sub2::run]"<<endl;
SegmentTreeRange<Node> seg(vector<Node>(N, 0));
vector<U> ans(Q, 0);
for (int q = 0; q < Q; ++q) {
if (O[q] == 1) {
Func f;
f.as[0] = 1;
seg.ch(L[q], R[q], &Node::apply, f);
} else if (O[q] == 2) {
Func f;
f.as[1] = 0;
seg.ch(L[q], R[q], &Node::apply, f);
} else if (O[q] == 3) {
const auto res = seg.get(L[q], R[q]);
Func f;
f.vs[res.cnts[0] ? 0 : 1] = V[q];
seg.ch(L[q], R[q], &Node::apply, f);
} else {
const auto res = seg.get(L[q], R[q]);
ans[q] = res.sum;
}
}
return ans;
}
} // sub2
namespace sub4 {
struct Node {
int mn;
int lz;
Node() : mn(M), lz(-1) {}
void push(Node &l, Node &r) {
if (~lz) {
l.paint(lz);
r.paint(lz);
lz = -1;
}
}
void pull(const Node &l, const Node &r) {
mn = min(l.mn, r.mn);
}
void paint(int val) {
mn = val;
lz = val;
}
};
vector<U> run(int Q0) {
cerr<<"[sub4::run] Q0 = "<<Q0<<endl;
SegmentTreeRange<Node> seg(N);
vector<vector<int>> qss(M);
for (int q = 0; q < Q0; ++q) qss[X[q]].push_back(q);
for (int x = M; --x >= 0; ) {
vector<int> is;
is.push_back(0);
is.push_back(N);
for (const int q : qss[x]) {
is.push_back(L[q]);
is.push_back(R[q]);
}
sort(is.begin(), is.end());
const int isLen = is.size();
SegmentTreeRange<Node> sub(isLen - 1);
sub.ch(0, isLen - 1, &Node::paint, x);
for (const int q : qss[x]) {
const int posL = lower_bound(is.begin(), is.end(), L[q]) - is.begin();
const int posR = lower_bound(is.begin(), is.end(), R[q]) - is.begin();
sub.ch(posL, posR, &Node::paint, (O[q] == 1) ? M : x);
}
for (int j = 0; j < isLen - 1; ++j) {
if (sub.get(j, j + 1).mn == x) {
seg.ch(is[j], is[j + 1], &Node::paint, x);
}
}
}
vector<vector<int>> iss(M + 1);
for (int i = 0; i < N; ++i) {
iss[seg.get(i, i + 1).mn].push_back(i);
}
vector<int> xs3(Q, -1);
// size [0, K): small, [K, N]: large
int K = 0;
{
vector<Int> freqSz(N + 1, 0);
for (int x = 0; x <= M; ++x) {
++freqSz[iss[x].size()];
}
vector<Int> freq3(N + 1, 0);
Int cnt4 = 0;
for (int q = Q0; q < Q; ++q) {
if (O[q] == 3) {
xs3[q] = seg.get(L[q], R[q]).mn;
++freq3[xs3[q]];
} else {
++cnt4;
}
}
Int now = cnt4 * N;
Int mn = now;
for (int k = 0; k <= N; ++k) {
now += freq3[k] * k;
now -= cnt4 * freqSz[k];
if (chmin(mn, now)) {
K = k + 1;
}
}
}
cerr<<"xs3 = "<<xs3<<endl;
// cerr<<"K = "<<K<<endl;
vector<U> bit(N, 0);
vector<int> xsLarge;
vector<vector<pair<U, U>>> bits(M + 1);
for (int x = 0; x <= M; ++x) if ((int)iss[x].size() >= K) {
xsLarge.push_back(x);
bits[x].assign(iss[x].size(), make_pair(0, 0));
}
auto add = [&](int x, int i, U val1) -> void {
const int pos = lower_bound(iss[x].begin(), iss[x].end(), i) - iss[x].begin();
const U val0 = -pos * val1;
for (int y = pos; y < (int)bits[x].size(); y |= y + 1) {
bits[x][y].first += val0;
bits[x][y].second += val1;
}
};
auto get = [&](int x, int i) -> U {
const int pos = lower_bound(iss[x].begin(), iss[x].end(), i) - iss[x].begin();
U ret0 = 0, ret1 = 0;
for (int y = pos; y > 0; y &= y - 1) {
ret0 += bits[x][y - 1].first;
ret1 += bits[x][y - 1].second;
}
return ret0 + ret1 * pos;
};
vector<U> ans(Q, 0);
for (int q = Q0; q < Q; ++q) {
if (O[q] == 3) {
const int x = xs3[q];
if ((int)iss[x].size() < K) {
for (const int i : iss[x]) {
bAdd(bit, i, V[q]);
}
} else {
add(x, L[q], +V[q]);
add(x, R[q], -V[q]);
}
} else {
ans[q] += bSum(bit, L[q], R[q]);
for (const int x : xsLarge) {
ans[q] -= get(x, L[q]);
ans[q] += get(x, R[q]);
}
}
}
return ans;
}
} // sub4
int main() {
for (; ~scanf("%d%d", &N, &Q); ) {
O.resize(Q);
L.resize(Q);
R.resize(Q);
X.assign(Q, -1);
V.assign(Q, 0);
for (int q = 0; q < Q; ++q) {
scanf("%d%d%d", &O[q], &L[q], &R[q]);
--L[q];
if (O[q] == 1 || O[q] == 2) {
scanf("%d", &X[q]);
--X[q];
} else if (O[q] == 3) {
scanf("%llu", &V[q]);
}
}
M = max(*max_element(X.begin(), X.end()), 0) + 1;
cerr<<"N = "<<N<<", M = "<<M<<", Q = "<<Q<<endl;
int Q0 = Q;
for (int q = 0; q < Q; ++q) if (O[q] == 3 || O[q] == 4) {
Q0 = q;
for (int qq = q; qq < Q; ++qq) if (!(O[qq] == 3 || O[qq] == 4)) {
Q0 = -1;
}
break;
}
vector<U> ans;
if (~Q0) {
ans = sub4::run(Q0);
} else if (M <= 1) {
ans = sub2::run();
} else {
ans = brute::run();
}
for (int q = 0; q < Q; ++q) if (O[q] == 4) {
printf("%llu\n", ans[q]);
}
#ifdef LOCAL
const auto brt=brute::run();
for(int q=0;q<Q;++q)if(brt[q]!=ans[q]){cerr<<q<<": "<<brt[q]<<" "<<ans[q]<<endl;break;}
assert(brt==ans);
#endif
}
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 50ms
memory: 26952kb
input:
1000 1000 3 722 914 2141556875752121755 3 323 347 6433743606947304931 2 142 206 439 2 117 840 195 2 127 502 56 3 168 707 15142638115094015116 4 190 257 2 88 976 475 1 319 867 351 1 682 889 409 2 406 446 196 3 28 35 4899387534800369959 2 291 546 150 1 528 617 128 1 58 122 251 2 381 400 276 4 510 958 ...
output:
15128467772367689008 17361914246216994339 5483226026482017320 3033562207293358603 2081407883485577238 7431958406282818646 4664359672511637691 8517692808398202534 17884251128335023776 3389445997760709607 15161173652136060523 17246899135664170339 16659472119973467421 5618344994614112283 92650283427734...
result:
ok 288 tokens
Test #2:
score: 0
Accepted
time: 9ms
memory: 5956kb
input:
1000 1000 1 538 681 44 2 112 540 10 1 160 191 28 1 276 867 1 4 118 419 4 62 209 1 575 884 37 1 783 895 45 4 342 410 2 545 870 16 1 273 501 11 3 258 352 13270291835335737625 3 490 514 5208698592597571883 2 629 865 43 3 966 981 14431353048791951405 1 290 809 16 4 468 843 1 607 875 26 2 177 521 6 4 176...
output:
0 0 0 1090256298972435763 147836376791542005 2987455658418197192 17393388322162025577 0 15463425577465259729 5603739312727078592 9162759280430770517 5734982725161877299 17209386033616770563 4838930779004365643 849737692109005723 6426101344117061130 5419322161439603233 5062725202245147693 71096115354...
result:
ok 245 tokens
Test #3:
score: 0
Accepted
time: 3ms
memory: 4212kb
input:
1000 1000 3 99 666 17220025026447219412 4 5 483 3 749 845 16031212477837693538 3 133 609 17502764194597679430 1 20 226 5 4 251 561 4 633 824 4 200 311 4 519 771 1 441 468 4 1 143 922 2 3 125 229 12754000280540900298 1 498 505 6 1 363 450 3 2 271 554 3 1 114 704 4 2 120 814 2 3 690 982 45445988286128...
output:
7328512720450443476 7442164624875844502 14518824065043662144 15136137278022830944 9027578627713658176 14666047547670987011 9573739028108360400 15993305979184887208 14884581396130778517 17761136731703624839 13312122318790827838 14347674975080853967 17128890277609978434 9773479657321740818 15378095570...
result:
ok 256 tokens
Test #4:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
1000 1000 3 331 336 13313883338135403138 2 34 521 1 1 207 917 1 2 293 636 1 1 10 687 1 2 41 872 1 1 355 758 1 1 288 842 1 3 400 783 5775690383446019013 4 314 322 2 304 613 1 2 826 891 1 2 202 822 1 4 548 564 4 116 797 2 19 741 1 3 682 909 6383131735642614258 1 236 239 1 3 540 587 8352069600659472359...
output:
0 5953016150034565141 10352142132099319436 6096323733974212364 12116874695872864409 15347176369296045030 5941262347742323458 3620424356881155419 10127217571760838974 5461268237196718849 17374108689525300602 10962054618902200654 10589539750496832325 18040788904369214946 4431085881313941227 1086737541...
result:
ok 245 tokens
Test #5:
score: 0
Accepted
time: 51ms
memory: 26784kb
input:
1000 1000 4 508 569 3 464 647 9626512068323288850 1 261 912 260 4 11 44 4 277 438 4 284 694 2 58 226 212 1 457 503 39 2 706 712 21 4 284 619 1 512 792 423 2 157 161 53 4 277 536 1 366 980 414 1 316 876 190 3 371 886 9029081672906636708 4 194 444 2 745 753 461 3 213 319 890290010596372158 2 753 762 3...
output:
0 0 0 390789495368193264 7549612687959379704 1759106186637124642 4069257141547258216 0 17049456214560332466 12608950793396043246 15542879177249956503 5268553984485336740 3347535289204500833 1283339644428090794 900030301309717320 10617803241693535373 14165237887531480080 7981622196338660662 108862472...
result:
ok 249 tokens
Test #6:
score: 0
Accepted
time: 5ms
memory: 5720kb
input:
1000 1000 3 129 542 13655472611747991961 4 511 790 2 427 432 24 4 297 777 3 42 429 12538231273219784506 2 599 608 39 3 527 566 15984446643208694087 2 205 211 1 3 601 694 12523292657204424213 3 545 831 15344770091989840452 1 602 989 37 1 53 385 37 4 682 969 3 543 721 5478413773432004467 1 56 745 34 3...
output:
12700009880616055584 1938841074867628294 11101356538763217641 10137253135833169997 13873622059376146753 13337075822234643821 9115529121094266177 7669597812731439884 7653582597306726684 16408805096415770957 5310328737375184018 10833975347168974529 3499327095010911697 4157942280079245663 1226136409211...
result:
ok 237 tokens
Test #7:
score: 0
Accepted
time: 2ms
memory: 4344kb
input:
1000 1000 2 235 237 1 3 293 925 11446750964413798601 1 299 374 3 4 663 909 3 11 599 10235863487659693663 2 68 71 10 1 354 730 5 2 716 719 1 1 492 636 6 2 653 657 6 1 383 436 3 4 25 151 4 63 940 4 375 432 4 271 700 1 42 349 4 1 282 760 2 1 277 993 5 4 230 883 2 353 357 5 3 193 326 3721636915624045074...
output:
4995644932646857199 8682577773112482081 14198642487599396424 3213041208013041424 13539808857214091375 761700240778104149 303442926722239461 3516102455933096238 57413777171872180 7755609655116170430 4422876140281257386 5188821315335992835 12241893756112962715 16177149822898993950 340672744116294775 1...
result:
ok 262 tokens
Test #8:
score: 0
Accepted
time: 4ms
memory: 7616kb
input:
1000 1000 2 677 685 1 3 323 762 12895483491686386027 3 298 384 18175344572520049422 4 502 504 2 82 84 5 4 366 888 4 446 447 1 215 667 2 4 74 288 4 713 832 1 647 758 6 2 814 823 2 4 335 545 3 549 653 4845209895729503532 3 727 749 2017173238814894361 3 106 331 7491311112690514667 4 383 640 1 306 501 3...
output:
1792962327640054849 4602247259348913401 7344222909663220438 0 17584876078194546406 14152406924757806061 9115461223074385858 16394226226497421375 11880805806882569475 6738114177990764802 6873497294390714416 4519670768317052046 12682237596341027497 12763260220853210949 6314086074882193678 149826222253...
result:
ok 241 tokens
Test #9:
score: 0
Accepted
time: 3ms
memory: 6752kb
input:
1000 1000 1 34 37 5 3 126 206 14727478235725604056 3 654 744 18255408097680139947 1 480 887 3 2 949 957 12 2 73 73 4 2 475 479 13 2 629 633 60 2 855 863 17 4 693 699 2 841 848 16 4 99 497 2 591 593 11 4 475 475 3 662 665 9880886915713059518 2 759 767 7 3 138 500 17769308332561790789 2 377 385 1 1 63...
output:
17107392241503669933 12334116376362625112 0 6456951739835200564 9971073695561689148 2802027920063294567 1036164630077188382 17606737366739661456 3673719133547364878 14283911652166609210 10307419488382662895 7570930610113533112 4760136262978142135 2686644875969537451 16340864373011062989 166150323341...
result:
ok 238 tokens
Test #10:
score: 0
Accepted
time: 4ms
memory: 5412kb
input:
1000 1000 1 72 236 30 1 50 509 27 1 13 108 25 2 886 894 4 3 655 875 4803545865429381065 3 383 783 11671115136637467033 1 585 927 23 2 504 509 1 1 30 147 26 2 741 749 16 4 270 679 4 173 186 2 144 145 23 3 221 230 3690281936266615260 3 239 771 8308954142750294924 3 563 791 15967473094317050982 2 223 2...
output:
7741491917409221922 0 1184088091910697156 9402573550842177896 16347258322020142583 10075791157671528329 15790910225201268145 3569527660563963307 15857736879027467782 12504414326160398443 10919437795207910592 16960732844939675104 17997032562817801024 8392051279069707625 5000292839030073720 1114739402...
result:
ok 235 tokens
Subtask #2:
score: 15
Accepted
Test #11:
score: 15
Accepted
time: 259ms
memory: 63116kb
input:
300000 300000 1 237576 237663 1 3 16150 16208 9270412155482010138 2 175648 175692 1 4 190836 190849 4 199010 199097 1 73976 298801 1 3 89902 89939 6418828085116455990 3 55415 55461 12238963685511262676 3 119825 119875 8146944792877919309 3 135103 135158 218634681842812119 3 127261 127352 13291431184...
output:
0 0 0 0 0 0 12272376591028786218 0 0 0 0 0 0 0 0 0 0 0 0 0 0 954290611784159519 0 3778617232493240005 8956067326602310519 7373452729428553855 16938285947326957203 0 0 14783754218831034862 7601682967357904165 0 0 0 0 0 0 11584905325916393312 0 0 4657169178464751085 17170356428308894805 0 0 0 0 148107...
result:
ok 74906 tokens
Test #12:
score: 0
Accepted
time: 254ms
memory: 63116kb
input:
300000 300000 3 51867 51899 1302529772508711959 1 163791 163805 1 1 176666 176684 1 2 127516 127575 1 4 31898 31983 3 151469 151497 15873092426332082486 3 206515 206568 14236701547576343621 4 238241 238324 3 61219 262809 1734847965363776922 2 220344 220393 1 2 98688 148993 1 4 55989 56049 3 298350 2...
output:
0 0 0 10681306550146550313 6652613657187526474 11475494508458717824 811486215804201182 1622972431608402364 0 15901103964711581888 3357820396972179286 4094176851202742427 5379446566603537422 16250215233565986824 15431111627897858304 0 16250215233565986824 4917765691823749552 0 0 10297212258427286974 ...
result:
ok 74943 tokens
Test #13:
score: 0
Accepted
time: 259ms
memory: 63240kb
input:
300000 300000 4 86816 86819 1 226565 246677 1 3 251963 251987 4817512795078102720 3 17122 202813 12262635941537918815 4 101129 101139 4 171789 171859 2 44072 166207 1 3 171011 171050 9516143677767859845 3 222046 222082 7458232785251868808 4 52499 166730 3 222551 222640 2035040917841558853 1 242195 2...
output:
0 5761786840950245653 3650180384843309913 13470892551030562504 16546298263213309450 3861341030454003487 15279334389549148006 5972947486560939227 0 11734734327511184880 0 10784511422263063797 16229557294797269089 3861341030454003487 10256609808236329862 15173754066743801219 0 1804317071900187272 5936...
result:
ok 74976 tokens
Test #14:
score: 0
Accepted
time: 253ms
memory: 63264kb
input:
300000 300000 2 224303 224374 1 3 5249 5288 16547079035307299489 1 249405 249440 1 1 244932 244988 1 1 89040 89114 1 2 114166 114194 1 4 110077 110172 1 141920 141970 1 3 205203 205243 1118749945144490180 2 127281 127373 1 3 173359 173363 11110846146456890394 3 283255 283303 3242183420586937197 3 12...
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 2204476432060505976 0 0 0 0 0 0 0 0 0 6246016557504766932 3429185560983009296 0 0 0 0 0 0 0 0 8450492989565272908 0 0 0 244941825784500664 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10672427856181146758 0 0 14782553786312832860 0 0 0 2449418257845006640 0 0...
result:
ok 74803 tokens
Test #15:
score: 0
Accepted
time: 220ms
memory: 63216kb
input:
300000 300000 1 220731 220734 1 3 219129 219133 1441661622928400529 4 297901 297906 3 226862 226869 2997910990656207321 2 154071 154073 1 1 239514 239523 1 2 264617 264626 1 1 66677 66680 1 2 108520 108527 1 2 493 498 1 3 93536 93536 1729223806369067100 1 99697 99702 1 1 98817 98817 1 2 268169 26817...
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 8523192685433180568 8523192685433180568 1420532114238863428 8523192685433180568 0 0 9943724799672043996 0 11364256913910907424 0 8523192685433180568 5682128456955453712 9943724799672043996 14205321142388634280 2841064228477726856 ...
result:
ok 74996 tokens
Test #16:
score: 0
Accepted
time: 300ms
memory: 63088kb
input:
300000 300000 3 242005 245455 17402857150844839475 1 195499 202760 1 3 86348 87652 16350042050962992455 2 67513 70549 1 2 17581 20392 1 1 180566 187399 1 2 132424 136215 1 4 201 7568 4 29035 34787 4 159930 167082 4 117096 126668 3 115807 124052 6966836812432990399 4 24003 25402 3 16679 17045 1443793...
output:
0 0 0 0 0 0 0 0 0 0 1069304592552696348 0 0 0 0 0 18416266141863826215 0 0 0 3291332335248161760 0 355153960082695408 2339117343903337888 0 0 8313068146843994614 0 0 1842567308665326891 0 8807430591712594964 2810662510187183646 0 0 11269033645696727616 11110474990560302869 4659943295138724138 573269...
result:
ok 75196 tokens
Test #17:
score: 0
Accepted
time: 272ms
memory: 63156kb
input:
300000 300000 2 129524 130230 1 3 97829 98681 14177044200280537874 1 117004 117036 1 3 75080 75625 7953158225766026866 3 222342 223044 592691174623108465 4 297810 298422 4 182525 182999 4 107197 107449 4 26126 26883 3 292284 292507 2229113056122186954 2 80055 80745 1 1 9570 10222 1 2 171443 171566 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6310142178115801295 0 0 0 0 0 0 0 0 0 14347829830854147244 0 0 0 0 0 0 0 0 3944750402169235976 0 0 14757788959901029185 1019326869378140182 0 0 0 0 10461260111479654801 0 0 16943243282109390662 0 0 0 7444098211629495683 16417881432838763511 10033696365246380464 15743721...
result:
ok 74887 tokens
Test #18:
score: 0
Accepted
time: 339ms
memory: 63332kb
input:
300000 300000 3 60899 273136 17900506015963226324 2 255340 262254 1 1 47804 166274 1 2 228603 279002 1 1 229031 276929 1 4 136197 298489 3 162024 257244 7401373630232006099 1 215974 227652 1 3 119149 204343 7745371782660146547 1 152630 214299 1 3 96818 230022 73641545834168695 1 216242 238152 1 4 84...
output:
18154335184155868016 4395498840986882932 6677517497004993358 9589498140629496089 7527637927391730952 7561535112473928655 10721089906023321737 14674898849238760964 7537937300108454874 2088977973872526664 12681955574796639580 865433786514001673 6128943734780039177 6057697509332298715 66303342836821411...
result:
ok 74979 tokens
Test #19:
score: 0
Accepted
time: 219ms
memory: 62320kb
input:
290000 290000 4 133423 133423 1 114519 114520 1 2 184800 184802 1 2 138774 138775 1 4 157293 157294 3 81666 81668 13806851267434892022 2 116280 116281 1 1 163245 163247 1 3 289833 289835 244401869236287882 3 135164 135164 8097051466237243604 1 113225 113226 1 4 43898 43900 4 289121 289121 2 133889 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 72459 tokens
Test #20:
score: 0
Accepted
time: 220ms
memory: 62364kb
input:
290000 290000 4 130502 130504 2 15321 15322 1 3 275364 275364 4162744751939177223 4 99544 99545 4 100620 100621 3 193438 193439 13148803698890728003 2 125274 125275 1 2 241880 241882 1 3 168292 168292 2833035078327940594 3 27814 27816 10620786078931893277 4 136822 136823 3 56337 56338 74789752446323...
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 15159374354299362052 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 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 72567 tokens
Subtask #3:
score: 0
Time Limit Exceeded
Dependency #2:
100%
Accepted
Test #21:
score: 0
Time Limit Exceeded
input:
300000 300000 3 19765 150566 5167493634543664094 2 118662 201848 4 4 127772 255639 1 363 249365 3 3 11598 175102 16530837351901358978 4 36444 234550 2 60767 191641 3 3 76143 190023 11283165360234648940 4 151255 257891 3 69394 97478 6131272952305682140 1 45277 77429 3 2 6151 122134 2 4 48165 93810 4 ...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #31:
score: 0
Time Limit Exceeded
input:
300000 300000 1 85444 86076 59 1 41150 41411 71 1 278698 279414 45 1 238445 239202 56 1 29965 29984 49 1 282953 283272 37 1 34668 35653 86 2 198587 198744 28 1 270855 271611 58 1 2130 2965 773 1 161601 162298 937 1 50299 50435 36 1 100759 101198 64 1 120208 120543 84 1 295293 295732 34 1 112185 1129...
output:
result:
Subtask #5:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #41:
score: 0
Time Limit Exceeded
input:
40000 40000 4 576 27541 4 6386 23009 1 20941 21376 751 3 823 32062 5063552653037376179 2 13664 17318 2188 1 8143 18546 1303 1 96 22011 1709 2 20800 37184 3499 3 4098 33457 11559569033571630334 1 6686 15115 2973 3 11874 14936 5095502711361186497 4 423 21401 2 465 17984 1744 4 7029 8301 2 11477 13949 ...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%