QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#85340 | #4817. Half Plane | Scintilla | TL | 8199ms | 63560kb | C++14 | 9.7kb | 2023-03-07 16:30:13 | 2023-03-07 16:30:15 |
Judging History
answer
#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 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;
void init() {
a = read(), b = read(), c = -read();
}
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;
}
frac k() {
return frac(-a, b);
}
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, pre[N], suf[N], h[N], key[N], rk[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() % (1 << 30);
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 = 1;
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: 7ms
memory: 62304kb
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: 12ms
memory: 62328kb
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: 7955ms
memory: 63424kb
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: 8032ms
memory: 63424kb
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: 7903ms
memory: 63460kb
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: 7770ms
memory: 63440kb
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: 7847ms
memory: 63464kb
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: 7898ms
memory: 63464kb
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: 8018ms
memory: 63492kb
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: 8052ms
memory: 63464kb
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: 8199ms
memory: 63464kb
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: 6455ms
memory: 63560kb
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: 6188ms
memory: 63492kb
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: -100
Time Limit Exceeded
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...