QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85365#4817. Half PlaneScintillaTL 11863ms88156kbC++149.7kb2023-03-07 17:39:312023-03-07 17:39:34

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-07 17:39:34]
  • 评测
  • 测评结果:TL
  • 用时:11863ms
  • 内存:88156kb
  • [2023-03-07 17:39:31]
  • 提交

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: 16ms
memory: 67024kb

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: 11ms
memory: 66956kb

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: 194ms
memory: 68672kb

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: 200ms
memory: 68636kb

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: 194ms
memory: 68596kb

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: 172ms
memory: 68632kb

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: 136ms
memory: 68628kb

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: 173ms
memory: 68724kb

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: 185ms
memory: 68520kb

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: 118ms
memory: 68760kb

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: 114ms
memory: 68668kb

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: 101ms
memory: 68488kb

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: 95ms
memory: 68476kb

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: 11863ms
memory: 88156kb

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: -100
Time Limit Exceeded

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: