QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#85366 | #4817. Half Plane | Scintilla | AC ✓ | 11852ms | 88900kb | C++14 | 9.7kb | 2023-03-07 17:42:13 | 2023-03-07 17:42:13 |
Judging History
answer
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb emplace_back
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl
using ull = unsigned long long;
using pii = pair <int, int>;
const int INF = 0x3f3f3f3f;
const int P = 1e9 + 7;
const int N = 6e5 + 10;
const int M = 3e4 + 10;
int read() {
int x = 0, f = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
return x * f;
}
int inc(int a, int b) { return (a += b) >= P ? a - P : a; }
int dec(int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul(int a, int b) { return 1ll * a * b % P; }
int qpow(int a, int b) { int res = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a); return res; }
mt19937_64 rng(time(0));
int Rand(int l, int r) {
return l + rng() % (r - l + 1);
}
struct Data {
int val[3];
Data() {
rep(i, 0, 2) val[i] = 0;
}
int& operator [] (int i) {
return val[i];
}
void init() {
rep(i, 0, 2) val[i] = read();
}
void add_eq(Data a) {
rep(i, 0, 2) val[i] = inc(val[i], a[i]);
}
void add(Data a, Data b) {
rep(i, 0, 2) val[i] = inc(a[i], b[i]);
}
void clr() {
*this = Data();
}
void print() {
rep(i, 0, 2) printf("%d%c", val[i], " \n"[i == 2]);
}
bool empty() {
Data e = Data();
rep(i, 0, 2) {
if (val[i] != e[i]) return false;
}
return true;
}
} ;
struct Operation {
int val[3][3];
Operation() {
rep(i, 0, 2) rep(j, 0, 2) val[i][j] = i == j;
}
int* operator [](int i) {
return val[i];
}
void init() {
rep(i, 0, 2) rep(j, 0, 2) val[i][j] = read();
}
void apply(Data &a) {
Data res;
rep(i, 0, 2) rep(j, 0, 2) {
res[i] = inc(res[i], mul(val[i][j], a[j]));
}
a = res;
}
void apply(Operation &a) {
Operation res;
rep(i, 0, 2) res[i][i] = 0;
rep(i, 0, 2) rep(j, 0, 2) rep(k, 0, 2) {
res[i][j] = inc(res[i][j], mul(val[i][k], a[k][j]));
}
a = res;
}
void clr() {
*this = Operation();
}
bool empty() {
Operation e = Operation();
rep(i, 0, 2) rep(j, 0, 2) {
if (val[i][j] != e[i][j]) return false;
}
return true;
}
void print() {
rep(i, 0, 2) rep(j, 0, 2) {
cout << val[i][j] << " \n"[j == 2];
}
}
} ;
struct frac {
int p, q;
frac(int _p = 0, int _q = 1) {
// cerr << "_p, _q = " << _p << ' ' << _q << endl;
p = _p, q = _q;
// int g = __gcd(p, q);
// p /= g, q /= g;
if (q < 0) p = -p, q = -q;
// cerr << "p, q = " << p << ' ' << q << endl;
}
friend bool operator < (frac a, frac b) {
return 1ll * a.p * b.q < 1ll * b.p * a.q;
}
friend bool operator == (frac a, frac b) {
return 1ll * a.p * b.q == 1ll * b.p * a.q;
}
void print() {
printf("%d/%d\n", p, q);
}
} ;
struct vec {
int x, y;
void init() {
x = read(), y = read();
}
friend bool operator < (vec a, vec b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
void print() {
printf("(%d, %d)\n", x, y);
}
} ;
struct line {
int a, b, c;
frac k;
void init() {
a = read(), b = read(), c = -read();
k = frac(-a, b);
}
bool chk(vec p) {
return a * p.x + b * p.y + c < 0;
}
bool above(vec p) {
// cout << "x, y, a, b, c = " << p.x << ' ' << p.y << ' ' << a << ' ' << b << ' ' << c << endl;
if (b > 0) return a * p.x + b * p.y + c < 0;
else return a * p.x + b * p.y + c > 0;
}
friend bool operator < (line l1, line l2) {
if (l1.k == l2.k) return frac(-l1.c, l1.b) < frac(-l2.c, l2.b);
else return l2.k < l1.k;
}
} ;
frac inter(line l1, line l2) {
return frac(l2.c * l1.b - l1.c * l2.b, l1.a * l2.b - l2.a * l1.b);
}
#define ls lson[u]
#define rs rson[u]
int tot, lson[N], rson[N];
vec p[N];
Data dat[N];
Operation laz[N];
void down(int u, Operation o) {
o.apply(dat[u]);
o.apply(laz[u]);
}
void pushdown(int u) {
// cout << "pushdown u = " << u << endl;
// rep(i, 0, 2) rep(j, 0, 2) {
// cout << laz[u][i][j] << " \n"[j == 2];
// }
down(ls, laz[u]);
down(rs, laz[u]);
laz[u].clr();
}
void maintain(int u) {
p[u] = p[ls];
dat[u].add(dat[ls], dat[rs]);
}
int newnode() {
return ++ tot;
}
void undo() {
pushdown(tot);
lson[tot] = rson[tot] = 0;
p[tot] = vec();
dat[tot].clr();
-- tot;
}
struct O {
int id;
line l;
Operation o;
} op[N];
int n, m, B, rk[N];
ull pre[N], suf[N], h[N], key[N];
void solve(int l, int r, vector <int> c) {
// cout << "----- solve l, r = " << l << ' ' << r << endl;
// cout << "c : ";
// for (auto it : c) cout << it << ' ';
// cout << endl;
int len = r - l + 1, cur = tot;
auto work = [&]() {
for (auto it : c) h[it] = 0;
vector <int> ord;
rep(i, l, r) ord.pb(i);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return op[i].l < op[j].l;
});
// pa(ord, 0, len - 1);
rep(i, 0, len - 1) {
key[ord[i]] = rng() % (1ll << 60);
pre[ord[i]] = i ? pre[ord[i - 1]] : 0;
if (op[ord[i]].l.b < 0) pre[ord[i]] ^= key[ord[i]];
rk[ord[i]] = i;
}
drep(i, len - 1, 0) {
suf[ord[i]] = i < len - 1 ? suf[ord[i + 1]] : 0;
if (op[ord[i]].l.b > 0) suf[ord[i]] ^= key[ord[i]];
}
sort(c.begin(), c.end(), [&](int i, int j) {
return p[i] < p[j];
});
vector <pair <frac, pii> > px;
rep(i, 0, len - 1) rep(j, i + 1, len - 1) if (op[ord[j]].l.k < op[ord[i]].l.k) {
// cout << "i, j = " << i << ' ' << j << endl;
// auto it = inter(op[ord[i]].l, op[ord[j]].l);
// it.print();
px.pb(mp(inter(op[ord[i]].l, op[ord[j]].l), mp(ord[i], ord[j])));
}
px.pb(mp(frac(INF, 1), mp(0, 0)));
sort(px.begin(), px.end(), [&](pair <frac, pii> a, pair <frac, pii> b) {
if (a.first == b.first) {
if (rk[a.second.first] == rk[b.second.first]) {
return rk[a.second.second] < rk[b.second.second];
}
else return rk[a.second.first] < rk[b.second.first];
}
else return a.first < b.first;
});
// for (auto it : px) {
// it.first.print();
// }
// pv(px.size());
// pa(ord, 0, len - 1);
for (int i = 0, j = 0; i < px.size(); ++ i) {
// pv(i);
// px[i].first.print();
for (; j < c.size() && p[c[j]].x < px[i].first; ++ j) {
// cout << "ord : ";
// for (auto it : ord) cout << it << ' ';
// cout << endl;
auto it = partition_point(ord.begin(), ord.end(), [&](int k) {
return !op[k].l.above(p[c[j]]);
});
// cout << "i, j = " << i << ' ' << j << endl;
// pv(c[j]);
// rep(k, 0, len - 1) {
// cout << "k, ord[k] = " << k << ' ' << ord[k] << endl;
// pv(op[ord[k]].l.above(p[c[j]]));
// }
if (it != ord.end()) h[c[j]] ^= suf[*it];
if (it != ord.begin()) h[c[j]] ^= pre[*(-- it)];
}
// pa(ord, 0, len - 1);
int u = px[i].second.first, v = px[i].second.second;
// cout << "u, v = " << u << ' ' << v << endl;
if (!u && !v) continue;
assert(rk[u] + 1 == rk[v]);
swap(ord[rk[u]], ord[rk[v]]);
swap(rk[u], rk[v]);
if (op[u].l.b < 0) pre[v] ^= key[u];
else suf[v] ^= key[u];
if (op[v].l.b < 0) pre[u] ^= key[v];
else suf[u] ^= key[v];
// pa(pre, 1, m);
// pa(suf, 1, m);
// px[i].first.print();
// pa(ord, 0, len - 1);
}
sort(c.begin(), c.end(), [&](int i, int j) {
return h[i] < h[j];
});
vector <int> nc;
for (int i = 0, j; i < c.size(); i = j + 1) {
for (j = i; j + 1 < c.size() && h[c[j + 1]] == h[c[i]]; ++ j) ;
if (i < j) {
rep(k, i + 1, j) {
int u = newnode();
ls = k == i + 1 ? c[i] : u - 1, rs = c[k];
maintain(u);
// pv(u);
// pv(ls);
// pv(rs);
// pa(dat[u], 0, 2);
// pa(dat[ls], 0, 2);
// pa(dat[rs], 0, 2);
}
nc.pb(tot);
}
else nc.pb(c[i]);
}
// pa(key, 1, m);
// pa(h, 1, n);
c = nc;
} ;
work();
// cout << "work done.\n";
// cout << "c : ";
// for (auto it : c) cout << it << ' ';
// cout << endl;
if (l == r) {
bool flag = false;
for (auto it : c) {
if (op[l].l.chk(p[it])) {
// pv(it);
// p[it].print();
dat[it].print();
down(it, op[l].o);
flag = true;
break;
}
}
if (!flag) printf("0 0 0\n");
while (tot > cur) undo();
return;
}
int mid = (l + r) >> 1;
solve(l, mid, c);
solve(mid + 1, r, c);
// cout << "tot, cur = " << tot << ' ' << cur << endl;
while (tot > cur) undo();
}
#undef ls
#undef rs
int main() {
n = read(), tot = n;
rep(i, 1, n) p[i].init(), dat[i].init();
m = read(), B = sqrt(n);
rep(i, 1, m) op[i].l.init(), op[i].o.init(), op[i].id = i;
// rep(u, 1, n) {
// rep(i, 0, 2) rep(j, 0, 2) {
// cout << laz[u][i][j] << " \n"[j == 2];
// }
// }
for (int l = 1, r; l <= m; l = r + 1) {
r = min(l + B - 1, m);
// cout << "l, r = " << l << ' ' << r << endl;
vector <int> all;
rep(i, 1, n) all.pb(i);
solve(l, r, all);
// pv(tot);
// rep(i, 1, n) {
// pa(dat[i], 0, 2);
// }
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 12ms
memory: 67016kb
input:
5 1 1 2 3 4 12 12 4 6 1 1 12 5 1 2 12 1 1 5 5 6 6 2 0 3 3 1 1 4 1 1 2 3 4 5 2 3 4 1 1 400 1 3 4 2 1 2 3 4 5 -1 -1 -10 3 2 1 4 6 5 4 3 2
output:
2 3 4 25 50 40 92 58 139
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 8ms
memory: 67008kb
input:
8 -509 1134 869419079 764178960 818736647 -2836 296 965929020 482991943 829626659 1594 -1045 289612318 572608619 474362463 -2946 -165 85255903 285022572 770151631 -74 -131 732523347 283776652 211209006 -627 -604 539714672 763810142 817996815 -1187 -1219 734874008 764773559 261445054 -18 226 31476550...
output:
242481509 621755738 615459217 984440526 242571329 417013116 122667367 215125161 518083968 594780462 21825000 214574293
result:
ok 4 lines
Test #3:
score: 0
Accepted
time: 179ms
memory: 68688kb
input:
30000 676 -1234 836467424 502287177 140023561 -2003 -54 939673593 585085650 422504901 14185 -49892 469301115 424738168 942143157 -6019 4933 573698653 956514739 385606216 -1097 -1767 918532462 279450765 873950517 -2732 5210 428418604 607751438 2805137 -2791 1240 250817926 463999452 951276698 -3460 -5...
output:
538200103 176562537 786040129 282120049 585253989 126746038 442585365 946639191 152848161 309217862 352168103 288017696 798331649 483116583 428411187 396357116 876189623 301235280 832917758 314259493 851554086 129794051 40695662 730810045 922712284 511389451 59925242 580263289 336968685 459480891 17...
result:
ok 1000 lines
Test #4:
score: 0
Accepted
time: 166ms
memory: 68736kb
input:
30000 -861 514 579191255 606538526 388715812 -2743 143 33760465 13211059 128903675 105 -1848 31959805 331710130 184775255 19 -1110 445507093 115980536 539879344 -1041 41 507163898 642632299 488129195 1471 81 294281682 547102977 542058890 804 -843 987425295 849386341 831783549 -1793 -2178 444562260 3...
output:
545178258 677491591 34959177 426445915 979131304 126183119 215187507 759685069 499663658 200968299 790214661 15389717 839830981 763311704 525155406 857030222 464548447 842171760 658456271 313959441 663157301 771261247 935340775 339842291 94545060 716008509 891433021 347612571 574108893 940930350 363...
result:
ok 1000 lines
Test #5:
score: 0
Accepted
time: 166ms
memory: 68712kb
input:
30000 10549 19178 551387003 459346332 265437020 -4440 -801 346488842 634142290 954669423 -1758 964 418335341 620928953 575285343 -4434 4081 109829333 799485017 24011325 -4527 -24166 664063304 756571635 986936785 -2020 -826 968644308 698506784 869326786 -2700 -7894 94755543 255350611 433336916 -6626 ...
output:
93567974 334118538 550727969 788441432 886909715 475552713 526828502 419035304 422234431 226030179 753442982 68364174 453395418 329482885 434105443 15411089 926245366 274889354 829805395 617738666 67824539 591388868 172923133 108968027 491445793 193764448 630342293 185049502 34074677 601638041 68749...
result:
ok 1000 lines
Test #6:
score: 0
Accepted
time: 158ms
memory: 68572kb
input:
30000 729570 -682315 124492027 232374133 480672372 -89810 -111355 986358898 821368981 395456251 167275 -156587 366703017 453206326 674212301 362570 -471220 637350218 819423356 510777066 -256566 369328 923342730 723162512 203219131 -85619 132807 403845003 932528656 550721085 58246 68727 988188769 670...
output:
177234170 706893826 321822432 51918258 607410764 301981413 520332556 577378859 923040905 748810147 59692955 792648057 715348611 655896889 617831176 601836304 718124476 848465506 797797405 409159165 810850490 467212419 781133102 681159662 508324225 694481060 155771698 74229267 592178614 439534413 690...
result:
ok 1000 lines
Test #7:
score: 0
Accepted
time: 134ms
memory: 68636kb
input:
30000 215276 568757 143058747 670589199 352546244 675349 276797 890016278 179562506 916859284 485993 366119 538889148 285689789 926460934 -184492 100853 168179724 850340050 328350589 542050 68798 786636421 318440051 561731640 226406 81944 652753350 969237706 547819021 -143180 485953 369758464 939858...
output:
365510556 899423656 472212247 119697678 211030227 547616991 943724197 8064634 987392937 751180665 973505281 385971334 146010557 420227720 902462073 950046809 985538196 710838208 550105062 384450812 364915306 671184632 124125952 829362702 960089545 335852503 982532966 451317766 825994835 31863551 648...
result:
ok 1000 lines
Test #8:
score: 0
Accepted
time: 159ms
memory: 68728kb
input:
30000 11963 26612 563932814 736535581 744632517 -2996 -641 649230390 398487502 776589770 1657 10623 794968118 747797397 59585526 -1289 4706 836020237 90456178 741776740 10179 -7004 847704879 346040819 168119367 21602 16579 515124205 829841195 234479530 -9495 4238 514818687 716733774 820045998 11361 ...
output:
847073709 381148374 516974732 325834948 765765564 453516874 352025353 10436598 371323304 519640707 574307750 444125010 964483737 141341740 498601658 122304331 399174936 431259077 742526585 700279913 545695293 236747120 378183966 111872419 373973546 315782774 219011044 653194034 928721309 678537800 1...
result:
ok 1000 lines
Test #9:
score: 0
Accepted
time: 165ms
memory: 68692kb
input:
30000 2313 20 151184035 531728233 996237244 515 -436 420930337 404861517 994681405 2926 -1322 689432222 234158944 272476457 52 530 390434030 44056866 776993283 -120 125 513404791 337625507 139274204 -1510 -588 855754494 303354450 351544403 291 419 471802575 810180275 84881798 -926 203 191026997 8895...
output:
935216674 480722085 384576623 621069889 322955919 600300871 538133841 334312373 608592766 399447778 295652105 484049427 606144001 591324118 339546480 453328653 101855275 823859765 818910344 986178644 528468199 516357332 825796558 402562947 380183389 14261509 250494299 809568025 37546310 730423078 16...
result:
ok 1000 lines
Test #10:
score: 0
Accepted
time: 122ms
memory: 68832kb
input:
30000 -3 0 18053028 724837864 201780269 4 -1 369642866 720614816 646577044 -2 3 992365366 938793416 407081706 1 -4 738991115 509688102 673930606 -5 -3 948082291 588327493 257752862 158959 -317919 21154757 755166158 63273074 -231604 463212 308429264 964756648 833312195 -274206 137101 54048637 8096471...
output:
862026374 343842668 392567836 26146542 777447884 265002500 519892143 987619881 426932515 307747538 901692231 98873625 299878208 896834820 396084450 518123452 367206424 423709655 492309974 426180612 43588029 93883631 234933962 816430356 941272925 469347297 418005544 712877801 820259786 207116902 6203...
result:
ok 1000 lines
Test #11:
score: 0
Accepted
time: 129ms
memory: 68672kb
input:
30000 -628784 -314394 968049914 611010155 822556658 -3 0 838684476 988751102 498207269 6 -1 158444020 203447175 827072499 -2 2 841964319 627180884 755281158 0 1 413763717 628446147 347356885 -284050 284052 94365801 261989175 608758104 -581295 -290648 374291550 717086259 564713688 73891 -55417 174966...
output:
957939759 686088484 588606155 357666270 89551368 871461447 304416932 448365469 240287435 189543262 819930261 29529388 991099953 449913997 43461210 477390988 422207149 985823068 562575922 578008854 565415569 204689372 295956274 353515327 903410183 296376364 476833877 243697219 390369978 573897742 136...
result:
ok 1000 lines
Test #12:
score: 0
Accepted
time: 81ms
memory: 68480kb
input:
30000 -999828 -999830 173576982 203686018 994555951 -998603 -998590 115320595 714379127 71972197 -998454 -998461 582494909 402300032 56908643 -999936 -999947 309327006 413646683 29938844 -998533 -998540 405243148 585079102 398415243 -999121 -999124 461176875 806714912 415591127 -999368 -999360 81873...
output:
706781663 971336842 722570837 901431625 707596220 681677130 732352331 871961411 695587377 408559767 167863511 861911926 896487900 934792684 147141981 493733093 18703611 340196993 985805162 566839384 988513262 491465851 966179587 213337874 679343318 939892014 685452506 271297173 725622566 526378994 4...
result:
ok 1000 lines
Test #13:
score: 0
Accepted
time: 79ms
memory: 68452kb
input:
30000 -998172 -998163 303367951 336827340 741891676 -998613 -998627 978906198 787402624 411749183 -999756 -999760 209847555 827753782 828064940 -998721 -998722 57298138 24146456 133315754 -999055 -999049 485766055 400319901 927614503 -999515 -999512 819375843 657191016 397525265 -998927 -998917 5628...
output:
344833859 511256074 589227250 160649192 831110888 812776997 364036365 231766374 134127815 561228840 82616806 21344553 492460416 411409491 673466870 81178955 7782751 53224357 668188185 936366293 846510789 447219778 260304026 996347527 195850491 714970045 82351025 519868498 352974360 74737778 46063511...
result:
ok 1000 lines
Test #14:
score: 0
Accepted
time: 11307ms
memory: 88132kb
input:
300000 6021 230 81186458 630223908 123502523 2206 -531 689274343 832968795 677935 -341 -5215 716916582 683843861 647948947 2201 -1132 238585560 881522585 759965041 -177 -1074 8264009 559321916 639075365 6108 6279 962302528 744228952 68956569 -4693 -2455 441948155 503678773 745829679 -420 -13854 4728...
output:
82983903 179991622 106488484 681002891 958372672 310322005 363534694 53035454 56365650 7875167 569276234 649871689 308858221 563321281 619554189 592339933 652542820 630728333 751354771 257358842 153279350 641615783 461178965 609603439 461431233 661609045 84919622 531356919 122787693 685566390 370288...
result:
ok 15000 lines
Test #15:
score: 0
Accepted
time: 11852ms
memory: 88192kb
input:
300000 -1541 2074 483711051 775771378 933380329 -1202 937 14941100 95502583 406917332 -397 933 119936225 788956255 184399251 -2102 3773 467131826 239645751 2290676 2072 -263 932141083 104521580 379780700 1158 -1549 370331747 922535291 448464108 -229 -2937 703381418 812044117 231275901 6736 6078 1912...
output:
151554358 46645906 509711997 957929736 124465982 921338614 780537979 152135527 222940084 898910633 706590019 155412491 666177849 668780531 141518722 120573053 841195759 693067816 673859081 914870171 539596578 797525561 762342396 893229210 666026033 522635102 678158674 324491661 430885376 143810029 2...
result:
ok 15000 lines
Test #16:
score: 0
Accepted
time: 11196ms
memory: 88112kb
input:
300000 -1429 3885 869722740 460347054 807234428 3210 -4073 740106320 769063122 1794249 -5330 999 825552652 687199472 471974260 3992 -13122 563236 12365054 26764156 5815 12317 619466573 742538443 90994367 3260 -11043 547395011 86980825 479243959 -4918 -5000 463639498 694648153 191692996 -8213 704 355...
output:
70369296 802723337 485242181 778408067 101136699 578430827 59236084 859831660 652901410 487792116 558581293 540295156 397927035 696155263 604985519 532561270 256798053 163000549 660547771 964952980 130194673 795610991 542049320 508344297 837462486 8411881 118887485 624170576 492134445 605006279 1220...
result:
ok 15000 lines
Test #17:
score: 0
Accepted
time: 10936ms
memory: 87944kb
input:
300000 -48956 176288 294568837 681990844 108484875 465540 30060 594194061 432722326 975809276 322853 86233 624880701 636519647 123533058 39572 123790 52446149 837375344 874805784 242075 16355 814153380 808465176 310264045 724220 141800 250042243 452069985 785962576 -15397 -302885 721918671 849665682...
output:
217164511 890555989 468580431 873672440 10416005 335152754 168260096 296116507 515183079 643587763 110241008 532159647 292054849 298856232 32579311 817235669 740795802 947667483 811580830 305170089 60911106 943907963 645552165 485781477 775206500 940421299 273866375 614646408 207555416 197985210 962...
result:
ok 15000 lines
Test #18:
score: 0
Accepted
time: 9011ms
memory: 84824kb
input:
300000 548861 388115 822669343 873492273 64551335 142114 483309 73323733 377207989 401490383 409937 433860 468438030 733460962 86587324 -95314 -724737 220585189 596749522 236182178 -232292 101582 962016830 94900027 376733896 -471250 -383514 546101196 384906647 735431088 -613815 -28324 935120004 2278...
output:
840102999 395990206 325451803 635747567 312896695 686169301 32392523 67192111 801889682 905088946 148676049 290362045 845729578 970554643 850798992 755069476 398969651 75952502 393532004 199951181 778505295 554172772 657233299 368574943 475330407 790333939 809810988 488164236 296809553 245848217 302...
result:
ok 15000 lines
Test #19:
score: 0
Accepted
time: 10414ms
memory: 88884kb
input:
300000 5682 9377 949323658 553347341 444480700 -558 12821 479233963 838560675 503993160 -90072 99174 64550749 372042921 157455703 33629 -18539 910752028 675178989 6183338 4094 -9068 571409045 855828101 666318228 7362 -3223 994148664 59458754 429764351 18143 15935 497100086 130510740 101003327 19627 ...
output:
134876512 996773578 290017641 12972555 545073419 36920150 163613612 148286639 953392953 549979315 813956825 439846140 461903687 393685137 111966526 384221517 205800294 614191703 398427965 265931649 896187620 398769200 244677051 117091887 858689143 583789209 164596528 320325883 648990746 692320533 91...
result:
ok 15000 lines
Test #20:
score: 0
Accepted
time: 10729ms
memory: 87828kb
input:
300000 547 690 346545624 337977798 795059761 45 -551 949642049 482808092 690979844 3219 -718 283653294 808205832 301230355 -642 434 137063134 719417339 556377894 1348 -877 935715166 762762998 429929218 -580 1119 98934045 111915923 121943244 -160 1552 415902936 660527333 715593097 562 267 940796772 8...
output:
676314820 153422372 531726977 957088456 516181215 376785017 411232593 251615075 698932972 872121538 638474993 392125420 184376465 170196693 682538955 162640120 365396981 315291403 899719122 784781991 193165169 900756271 249147967 727724517 558035587 964383737 923478314 673082882 410404532 216144252 ...
result:
ok 15000 lines
Test #21:
score: 0
Accepted
time: 6276ms
memory: 85072kb
input:
300000 -160874 -321740 650679894 682085901 118564431 1 3 829284607 674413386 589242129 -1 -5 128251902 861925529 227295077 2 0 483335001 136506986 627827042 373064 -186531 980063766 887583003 124536602 -556935 278464 203163296 576564387 284484406 0 -8 370263598 946662142 724897316 -322063 -161035 16...
output:
270929648 657292934 1072391 355748333 538055525 893060481 923071675 138126180 897616241 368606556 247572560 663225792 935528969 985474533 765493326 906004891 660594616 73269130 270889963 986581893 508328370 548082638 466247003 942212565 541968798 644553201 603406730 130543301 125334160 698875079 901...
result:
ok 15000 lines
Test #22:
score: 0
Accepted
time: 7732ms
memory: 85284kb
input:
300000 65295 -195880 385584455 694104346 148795395 -13 -17 488197125 209315462 279490886 -265924 66482 956139323 150523857 807174592 -10 -1 489624340 294113836 105155469 301777 -452671 177016278 761145479 618009928 -483086 483087 707376469 281943593 287178442 2 0 204033761 106059218 639213997 -61180...
output:
78838465 117908463 834181295 567509055 243808330 913222361 244968863 163827552 29820256 154896700 770138099 728655661 315086555 153737882 840149247 724261403 931639840 627022483 657782150 581792098 520940815 16423833 44322662 944662939 598320637 918035850 598728337 956869149 20662870 706170737 92870...
result:
ok 15000 lines
Test #23:
score: 0
Accepted
time: 3196ms
memory: 83548kb
input:
300000 -999985 -999984 771104286 637539159 323203410 -999930 -999940 788941295 790543578 678521431 -999997 -1000000 570602998 259724723 505592327 -999928 -999926 186482400 667942892 390211978 -999945 -999954 958616669 706098243 622246987 -999968 -999960 483002356 756786785 778047664 -999927 -999932 ...
output:
591071517 442832578 964585697 131194468 225150960 545438630 128272459 154095760 478240411 320650232 79107616 719175041 486515135 177636535 839480941 651280717 776056591 819483361 321866025 378471124 83934758 673281094 275690569 340822554 643704765 951851307 349176407 230158685 745653379 178123286 10...
result:
ok 15000 lines
Test #24:
score: 0
Accepted
time: 3307ms
memory: 83052kb
input:
300000 -999676 -999679 299330476 945554727 657777676 -999904 -999916 20053996 611803916 395817665 -999670 -999670 612731766 864724128 359400642 -999937 -999940 489607311 867858727 277218512 -999649 -999655 935906592 757715137 78332801 -999895 -999899 135123021 969130132 219960695 -999655 -999649 169...
output:
709554873 609165180 555956807 531357241 714224166 923404132 127543156 497814595 947821210 301695249 357344553 804158600 210468246 92645771 652991804 316278431 884960110 415712621 164978596 222153968 988524136 106053390 369509942 622807089 873613124 255812459 616511678 409751051 73665693 141378215 67...
result:
ok 15000 lines
Test #25:
score: 0
Accepted
time: 1676ms
memory: 71024kb
input:
65536 -128 -128 708578711 499407572 642979214 -128 -127 5380635 850194636 966346205 -128 -126 442014492 142528482 610486620 -128 -125 828136096 678175179 22530505 -128 -124 857359786 624737028 825258522 -128 -123 757405373 240905621 152449995 -128 -122 203888775 621532595 680687473 -128 -121 5865051...
output:
944158242 470610728 324244920 947225065 20496025 91607361 813293281 208911888 569449785 428221964 621131992 628199758 31116565 179087985 695555347 158594615 97325092 68183428 408860838 264156737 165049069 599382005 7206793 468343080 488058929 761025356 661014958 123067024 941391330 400777058 4817810...
result:
ok 10000 lines
Test #26:
score: 0
Accepted
time: 1701ms
memory: 71012kb
input:
65536 -128 -128 818210398 350781835 808267841 -128 -127 598893503 929012653 956329690 -128 -126 87366628 643195410 600522273 -128 -125 796246237 758640967 930653623 -128 -124 642577701 229239488 736734352 -128 -123 707428687 112318005 145500329 -128 -122 918542168 917677101 820610552 -128 -121 90255...
output:
855682198 211910937 39504531 682339758 422219265 456212785 21608811 299210296 409888641 186999437 896166393 317172847 877820550 219410090 708309892 328654979 945865162 607723625 399336057 110910736 627799030 63908341 751868626 60091881 502622849 875513884 466344371 608605021 283506714 277953532 6707...
result:
ok 10000 lines
Test #27:
score: 0
Accepted
time: 947ms
memory: 70740kb
input:
65536 -128 -128 321669782 130247468 561206790 -128 -127 586338406 194856392 107744466 -128 -126 131308995 725738615 9547769 -128 -125 468414571 779122301 704741042 -128 -124 589970087 691554526 435763847 -128 -123 765019622 297637752 766277236 -128 -122 768772892 351956378 376748837 -128 -121 217385...
output:
452238362 220635836 746985503 633072170 440058234 542058223 907080515 242487087 910036035 685519110 129478062 394899270 55462417 689975056 149618496 240204643 811436389 936545164 490369905 866444411 284153567 227518462 755988386 713973494 920668178 938766338 281737723 238078066 685725788 490649730 4...
result:
ok 10000 lines
Test #28:
score: 0
Accepted
time: 851ms
memory: 70788kb
input:
65536 -128 -128 431301469 276588999 17667414 -128 -127 179851266 568641678 806555954 -128 -126 67833135 935233540 704616161 -128 -125 731491980 859588089 202798683 -128 -124 375188003 587228991 933378949 -128 -123 420075667 464017404 349262100 -128 -122 483426279 353133617 516671916 -128 -121 537226...
output:
211966235 578279482 781544846 429714636 652539297 4320996 989365990 954279125 553787357 212146530 285860296 862484974 96926573 74014623 511632690 96404576 632735159 69659452 783703164 828444528 6879499 686760001 63051304 738376033 554907616 566374092 504484087 165864008 133776084 107140753 485715573...
result:
ok 10000 lines
Test #29:
score: 0
Accepted
time: 1852ms
memory: 81916kb
input:
300000 0 0 596981855 579443258 477525092 0 2 815869175 972934050 743291979 0 4 978860748 76319153 632768702 0 6 306834906 942121618 858912401 0 8 387540510 114700412 508251746 0 10 36256602 331228420 185902564 0 12 803824169 340723119 139573240 0 14 353565972 761261492 146228475 0 16 466786733 59456...
output:
608475874 971471451 630382617 211136806 81336083 766490611 995262791 87160153 28671548 293997269 612426055 584834410 394350234 917367029 864933496 54824456 240344520 675951953 849790890 437774062 942745218 649919302 238190182 155165269 255943586 501943472 375110461 635898015 716335644 547105804 2803...
result:
ok 15000 lines
Test #30:
score: 0
Accepted
time: 1860ms
memory: 81864kb
input:
300000 0 0 706613542 139645516 642813719 0 2 114414767 346719329 28242725 0 4 620417621 576986082 331632351 0 6 569912316 731415402 767035512 0 8 758897697 420440347 714694844 0 10 691312655 497608072 473920167 0 12 227305551 636867625 279496319 0 14 673407122 85726981 562738249 0 16 516647826 53255...
output:
478522684 850704721 42775037 972197898 133836878 153764286 547192203 361586578 506493931 729784777 872900800 783163091 366710007 227964936 792316751 394329763 198812111 10245245 147751517 779562109 562662671 701585197 281466482 921143289 595798079 189408529 756717355 236338796 73081228 70561406 1710...
result:
ok 15000 lines
Test #31:
score: 0
Accepted
time: 10985ms
memory: 88184kb
input:
300000 -2350 -3013 245675462 911378048 677362975 -358 -1385 585223865 818408768 422435834 1404 -1016 97087157 33014793 865923491 3214 -4102 973788862 635238160 214679469 -14075 4240 478390393 651257077 954350005 1670 -1280 899638249 497851197 445742566 720 -4482 434549131 651313696 854472472 1306 45...
output:
965858405 257261426 109123560 364237663 642045031 470762934 214912455 452993922 187120151 144207494 199137546 213132841 881082698 295259830 56824314 110294644 886267221 289200595 439326763 839800084 258705172 755433994 386134006 34508765 988958105 879862458 839908536 506235645 314709525 745914401 66...
result:
ok 15000 lines
Test #32:
score: 0
Accepted
time: 11426ms
memory: 88136kb
input:
300000 -2302 190 714995886 991088608 771990293 1014 85 231347730 542747622 134541710 -3310 1707 255951607 873272465 393426788 1018 -1244 982323740 223584309 355203619 638 996 117472513 670442187 316109785 1398 -1069 434150242 100290322 311294015 -976 582 926092587 539041159 311253467 1401 998 977699...
output:
458051332 222894922 632542639 996576604 436332126 677096767 533004139 206805363 141675540 448476031 883747960 242014768 760491187 322749269 964267014 639208139 961743089 13828085 989519473 946779167 568162719 793658482 68745626 385154053 77255667 797485920 330146602 809574245 860315828 475452623 373...
result:
ok 15000 lines
Test #33:
score: 0
Accepted
time: 11362ms
memory: 88900kb
input:
300000 6772 -15300 235980676 58877798 146257108 4095 7455 719702624 104531778 692144934 -36695 -13242 168908060 753219166 968936472 -2218 -1192 291504199 659962689 621579638 -1285 2233 544667828 492538481 481849967 -655 -1430 533437760 928093108 116284051 1479 -1437 365663907 764811847 93914417 7157...
output:
547154138 732249021 673486000 888884289 549656006 773460681 73834513 601743541 830036604 417673799 902083474 765199341 519486404 408403165 174211855 45670451 313653429 950733578 21340257 892976645 769723492 913680579 691513312 339583552 485678663 726031463 84403032 313999626 318902519 923903402 4969...
result:
ok 15000 lines
Test #34:
score: 0
Accepted
time: 10351ms
memory: 87812kb
input:
300000 115220 86640 609193479 302434012 22394158 -391 -70503 803048016 760371293 37973011 -67392 343436 244886174 583899088 882242632 560714 114828 518615698 715313998 94399409 -21830 181310 997166576 248502368 694763319 40150 -121754 62637961 224486026 745558881 67221 110717 693447109 9798016 45882...
output:
201600093 183607204 771639571 129652125 545101303 969375610 788167477 725027865 229184956 81233333 494233469 66621115 273959673 101167775 585290416 827958699 757666522 242277767 473919790 680542798 261772569 795797996 203721372 904611160 462186915 305058046 185446570 166114066 498521271 554538946 56...
result:
ok 15000 lines
Test #35:
score: 0
Accepted
time: 8587ms
memory: 84884kb
input:
300000 111350 443017 158808827 376761115 614329510 -97653 -699073 481682438 776135393 563312585 334069 325834 503974582 419117286 410048070 -91661 101509 881047510 53170370 739892500 -150820 -752747 433037934 945672768 306740646 -524852 278705 392150199 319206779 496205813 -178130 -28629 172189389 9...
output:
581294923 242817632 936401012 431037860 811658812 65127210 601945043 639422138 842848405 314564112 886535959 812556910 548115791 187390985 898843145 539509472 486057492 141733143 445896480 112949679 306559814 317129459 808857111 570035 83302897 129014172 990702370 204692059 809946524 795322018 96768...
result:
ok 15000 lines
Test #36:
score: 0
Accepted
time: 10583ms
memory: 88036kb
input:
300000 17576 -24307 581185987 901924920 267036504 5403 -8414 486177640 341809894 238657082 12228 1834 418950426 19746557 840661286 -7367 -37147 848084279 101445151 419510948 -1476 -10966 248160616 736116458 821164473 -5039 5722 643671042 11737615 22364656 -6927 6171 60700185 625685920 115812243 -839...
output:
93157683 129666402 165032323 275075573 399960799 621922143 327896783 583180727 549111133 613556504 695615462 434639292 109604816 194075542 321249522 610001749 292355842 848229107 330290018 46784925 750220800 903214311 794738940 625152817 785215182 140437065 909450955 584743914 896505574 821267297 89...
result:
ok 15000 lines
Test #37:
score: 0
Accepted
time: 10667ms
memory: 87868kb
input:
300000 821 -1089 397376108 866417645 124937321 -25 -104 201522775 629372122 21412667 2222 4683 242926747 757056677 71274423 -606 111 858008622 499358170 838682503 -1293 -814 887009168 7325898 834353710 -3629 -776 514576571 968228660 740151058 -837 112 209013563 292613247 500136458 107 82 558575219 9...
output:
615499773 436152353 401998327 35446237 739885469 948659097 62967612 735829517 504099057 982124397 234247445 787888837 842711401 585655887 703181052 92853025 290147258 776887418 867121044 136363853 95209801 125722478 363541636 509424481 657610365 362873327 591312176 432776125 905215709 598033075 2833...
result:
ok 15000 lines
Test #38:
score: 0
Accepted
time: 6335ms
memory: 85016kb
input:
300000 -40738 81487 331967802 82741171 966286568 1 -5 358342798 698097228 174193661 3 -1 362193443 704588389 595478314 0 -1 824624354 678819820 778453632 4 1 146518698 674014883 878467586 -222855 -111429 100825625 911901998 41788699 -64386 -32198 901183368 850328975 927107528 2 1 713432882 452725941...
output:
423403983 977193767 921040649 829919188 609962346 699555649 937712585 62912960 655712614 435815771 86221253 890566162 858426142 422549036 89966335 160814039 12854330 680380157 737662080 330073975 684678436 814817703 172583247 763569718 782191585 813624698 170080499 600355438 30697312 512021353 83977...
result:
ok 15000 lines
Test #39:
score: 0
Accepted
time: 7711ms
memory: 85220kb
input:
300000 -114533 114532 924415007 388541673 449773062 16 -8 644104868 551472959 795024387 -3 4 712060441 421873472 662640215 -1 0 430080686 690558550 136656034 6976 5230 402878063 85846043 415643291 0 2 895388418 512282055 979104476 0 1 727779542 227423436 895159386 9867 14805 385627768 982944714 8332...
output:
466101494 903569366 334769328 271638391 915938966 464423618 541933334 699263706 301444831 167553367 761528617 563945605 105256150 465824006 732836738 764512484 222790413 701757593 989080064 937828617 230564512 461752681 455817555 120237947 146668365 635098820 465104829 38548516 85635309 679852295 16...
result:
ok 15000 lines
Test #40:
score: 0
Accepted
time: 3291ms
memory: 85004kb
input:
300000 -999959 -999960 887172069 715590592 910705137 -999921 -999930 778196637 886301768 85219705 -999929 -999931 236033502 895271481 254172430 -999936 -999931 774652077 459165007 482096470 -999943 -999946 259807100 505990673 92757934 -999980 -999975 17951511 279571703 51055321 -999976 -999975 41581...
output:
970191661 521585630 565008771 182514132 850585301 95065808 393160936 539045163 742688747 533052596 951713993 312181914 378871730 621694012 682710054 762234342 105821044 842614998 715231584 90033696 788426771 402638334 546752099 85739839 379736023 59460506 893522473 938228203 114437634 894336152 7530...
result:
ok 15000 lines
Test #41:
score: 0
Accepted
time: 3234ms
memory: 82900kb
input:
300000 -999687 -999682 150011522 945777683 814170751 -999969 -999962 467924468 25246178 131509199 -999792 -999801 767864038 4561657 320011913 -999785 -999775 542135863 447736948 207208614 -999837 -999827 307902769 866598398 371705330 -999697 -999703 889709104 404635934 937321575 -999798 -999787 1550...
output:
259097185 892424434 324634999 933312298 768931020 113221640 278105398 237976001 232433349 119730417 471250584 145816716 976653796 640400157 313232226 223416848 529505621 898628379 470398626 854360251 983498041 15245902 428886420 635392136 21460781 385378735 100904271 884275064 153920670 783063111 48...
result:
ok 15000 lines
Test #42:
score: 0
Accepted
time: 11ms
memory: 67104kb
input:
1 335611 335626 973830257 495258238 637490447 1 -3 3 46 307267412 943972690 865059306 73069911 513416910 400977391 776349245 417271346 266127937
output:
973830257 495258238 637490447
result:
ok single line: '973830257 495258238 637490447'