QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85127#4817. Half PlaneScintillaWA 394ms63588kbC++149.3kb2023-03-06 23:48:432023-03-06 23:48:44

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-06 23:48:44]
  • 评测
  • 测评结果:WA
  • 用时:394ms
  • 内存:63588kb
  • [2023-03-06 23:48:43]
  • 提交

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 * a.q * b.p;
  }
  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 l1.c < l2.c;
    }
    else return l1.k() < l2.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> t, ord;
    rep(i, l, r) t.pb(i);
    sort(t.begin(), t.end(), [&](int i, int j) {
      line l1 = op[i].l, l2 = op[j].l;
      if (l1.k() == l2.k()) {
        return l1.c < l2.c;
      }
      else return l2.k() < l1.k();
    });
    // pa(t, 0, len - 1);
    rep(i, 0, len - 1) {
      key[t[i]] = rng() % (1 << 30);
      pre[t[i]] = i ? pre[t[i - 1]] : 0;
      if (op[t[i]].l.b < 0) pre[t[i]] ^= key[t[i]];
      ord.pb(t[i]), rk[t[i]] = i;
    }
    drep(i, len - 1, 0) {
      suf[t[i]] = i < len - 1 ? suf[t[i + 1]] : 0;
      if (op[t[i]].l.b > 0) suf[t[i]] ^= key[t[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[t[j]].l.k() < op[t[i]].l.k()) {
      // cout << "i, j = " << i << ' ' << j << endl;
      // auto it = inter(op[t[i]].l, op[t[j]].l);
      // it.print(); 
      px.pb(mp(inter(op[t[i]].l, op[t[j]].l), mp(op[t[i]].id, op[t[j]].id)));
    }
    px.pb(mp(frac(INF, 1), mp(0, 0)));
    sort(px.begin(), px.end());
    // 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 id) {
          return !op[id].l.above(p[c[j]]);
        });
        // cout << "i, j = " << i << ' ' << j << endl;
        // 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)];
      }
      int u = px[i].second.first, v = px[i].second.second;
      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);
      // 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(m);
  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: 62292kb

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: 13ms
memory: 62300kb

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: 394ms
memory: 63492kb

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: 369ms
memory: 63472kb

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: 359ms
memory: 63496kb

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: -100
Wrong Answer
time: 362ms
memory: 63588kb

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:

746579529 991268082 1525623
719751170 445508119 341222087
696205486 71418698 862668896
443373130 448853267 834095192
12762801 664136169 195047054
500200321 346739175 306308925
38659203 544548737 136482629
390338685 178622997 954133280
529026193 109143769 829328665
588184000 477926865 383883566
29008...

result:

wrong answer 1st lines differ - expected: '177234170 706893826 321822432', found: '746579529 991268082 1525623'