QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#85109#4817. Half PlaneScintillaRE 9ms62968kbC++149.1kb2023-03-06 23:19:202023-03-06 23:19:24

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:19:24]
  • 评测
  • 测评结果:RE
  • 用时:9ms
  • 内存:62968kb
  • [2023-03-06 23:19:20]
  • 提交

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) {
    p = _p, q = _q;
    if (q < 0) p = -p, q = -q;
    int g = __gcd(p, q);
    p /= g, q /= g;
  }
  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());
    // 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) {
    for (auto it : c) {
      if (op[l].l.chk(p[it])) {
        // pv(it);
        // p[it].print();
        dat[it].print();
        down(it, op[l].o);
        break;
      }
    }
    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 62968kb

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: 9ms
memory: 62636kb

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: -100
Dangerous Syscalls

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:


result: