QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352030#297. 里面还是外面debgxh80 517ms96064kbC++205.1kb2024-03-12 19:45:202024-03-12 19:45:29

Judging History

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

  • [2024-03-12 19:45:29]
  • 评测
  • 测评结果:80
  • 用时:517ms
  • 内存:96064kb
  • [2024-03-12 19:45:20]
  • 提交

answer

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
template <class int_t, class sqr_t = int_t>
struct vec2d{
  int_t x, y;
  vec2d(): x(0), y(0){}
  vec2d(int_t x, int_t y): x(x), y(y){}
  int quad() const {
    if(x > 0 && y >= 0) return 0;
    if(x <= 0 && y > 0) return 1;
    if(x < 0 && y <= 0) return 2;
    if(x >= 0 && y < 0) return 3;
    assert(false);
  }
  bool operator < (const vec2d &rhs) const {
    return quad() < rhs.quad() || (quad() == rhs.quad() && (*this) % rhs > 0);
  }
  vec2d operator + (const vec2d &rhs) const {return vec2d(x + rhs.x, y + rhs.y);}
  vec2d operator - (const vec2d &rhs) const {return vec2d(x - rhs.x, y - rhs.y);}
  sqr_t operator * (const vec2d &rhs) const {return (sqr_t)x * rhs.x + (sqr_t)y * rhs.y;}
  sqr_t operator % (const vec2d &rhs) const {return (sqr_t)x * rhs.y - (sqr_t)rhs.x * y;}
  vec2d& operator += (const vec2d &rhs){return *this = *this + rhs;}
  vec2d& operator -= (const vec2d &rhs){return *this = *this - rhs;}
  vec2d operator - () const {return vec2d(-x, -y);}
  sqr_t sqr() const {return (sqr_t)x * x + (sqr_t)y * y;}
}; typedef vec2d<int, int64_t> vec;
constexpr int MAXN = 50005;
int X; struct Line{
  vec L, R;
  Line(vec A, vec B): L(A), R(B){if(assert(A.x != B.x), A.x > B.x) swap(L, R);}
  friend bool operator < (const Line &m, const Line &n){
    int mDx = m.R.x - m.L.x, nDx = n.R.x - n.L.x;
    return (__int128)(X - m.L.x) * (m.R.y - m.L.y) * nDx + (__int128)m.L.y * mDx * nDx <
           (__int128)(X - n.L.x) * (n.R.y - n.L.y) * mDx + (__int128)n.L.y * mDx * nDx;
  }
};
vector<int> Vx;
struct SegTree{
  SegTree *ls, *rs;
  tree<Line, null_type, less<Line>, rb_tree_tag, tree_order_statistics_node_update> T;
  SegTree(int l = 0, int r = Vx.size() - 1): ls(nullptr), rs(nullptr){
    if(r - l > 1){
      int mid = (l + r) >> 1;
      ls = new SegTree(l, mid);
      rs = new SegTree(mid, r);
    }
  }
  int query(int id, const Line &m, int l = 0, int r = Vx.size() - 1){
    auto it = T.lower_bound(m); if(it != T.end() && !(*it < m) && !(m < *it)) return 0;
    int res = 1 - (T.order_of_key(m) & 1) * 2;
    if(r - l == 1){return res;} int mid = (l + r) >> 1;
    if(id < mid) return res * ls->query(id, m, l, mid);
    else         return res * rs->query(id, m, mid, r);
  }
  void insert(int l_, int r_, const Line &m, int l = 0, int r = Vx.size() - 1){
    if(l_ >= r || r_ <= l) return;
    if(l_ <= l && r_ >= r){X = (Vx[l] + Vx[r]) >> 1, T.insert(m); return;}
    int mid = (l + r) >> 1;
    ls->insert(l_, r_, m, l, mid);
    rs->insert(l_, r_, m, mid, r);
  }
  void erase (int l_, int r_, const Line &m, int l = 0, int r = Vx.size() - 1){
    if(l_ >= r || r_ <= l) return;
    if(l_ <= l && r_ >= r){X = (Vx[l] + Vx[r]) >> 1, T.erase (m); return;}
    int mid = (l + r) >> 1;
    ls->erase (l_, r_, m, l, mid);
    rs->erase (l_, r_, m, mid, r);
  }
}*T;
constexpr int MOD = 1000000000;
inline vec reduce(vec &A){return A = (A - vec(MOD >> 1, MOD >> 1)), A += A;}
inline vec unduce(vec &A){return A = vec(A.x >> 1, A.y >> 1) + vec(MOD >> 1, MOD >> 1);}
int n, m, Ans, O[MAXN], R[MAXN], LstX, LstY; vec A[MAXN], Q[MAXN][3];
void add(const vec &A, const vec &B){
  if(A.x != B.x){
    Line h(A, B);
    int l = lower_bound(Vx.begin(), Vx.end(), h.L.x) - Vx.begin();
    int r = lower_bound(Vx.begin(), Vx.end(), h.R.x) - Vx.begin();
    return T->insert(l, r, h);
  }
}
void del(const vec &A, const vec &B){
  if(A.x != B.x){
    Line h(A, B);
    int l = lower_bound(Vx.begin(), Vx.end(), h.L.x) - Vx.begin();
    int r = lower_bound(Vx.begin(), Vx.end(), h.R.x) - Vx.begin();
    return T->erase (l, r, h);
  }
}
int query(const vec &A){
  if(A.x < Vx.front() || A.x > Vx.back()) return 1;
  int id = max<int>(lower_bound(Vx.begin(), Vx.end(), X = A.x) - Vx.begin(), 1) - 1;
  int res = T->query(id, Line(vec(-MOD, A.y), vec(MOD, A.y)));
  return res;
}
int main(){
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> A[i].x >> A[i].y, Vx.push_back(reduce(A[i]).x);
  cin >> m;
  for(int i = 1; i <= m; i++){
    cin >> O[i]; if(!O[i]) cin >> R[i];
    for(int j = 0; j < 3; j++) cin >> Q[i][j].x >> Q[i][j].y;
    if(O[i]) reduce(Q[i][0]), reduce(Q[i][1]), Vx.push_back(reduce(Q[i][2]).x);
  } sort(Vx.begin(), Vx.end());
  assert(unique(Vx.begin(), Vx.end()) == Vx.end());
  T = new SegTree;
  for(int i = 1; i <= n; i++) add(A[i], A[i % n + 1]);
  vec P0(0, 0); switch(query(reduce(P0))){
    case -1: Ans = 0; break;
    case  0: Ans = 2; break;
    case  1: Ans = 1; break;
  }
  for(int i = 1; i <= m; i++) if(!O[i]){
    LstX = ((int64_t)R[i] * LstX + Q[i][Ans].x) % MOD;
    LstY = ((int64_t)R[i] * LstY + Q[i][Ans].y) % MOD;
    vec P(LstX, LstY); reduce(P); switch(query(P)){
      case -1: Ans = 0, cout <<  "in\n"; break;
      case  0: Ans = 2, cout <<  "bd\n"; break;
      case  1: Ans = 1, cout << "out\n"; break;
    }
  } else del(Q[i][0], Q[i][1]), add(Q[i][0], Q[i][2]), add(Q[i][1], Q[i][2]);
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 17ms
memory: 8436kb

input:

1000
249999750 499999500
749713536 249714036
748856394 248856894
748570680 248571180
248571180 498570930
247999752 497999502
247428324 497428074
246571182 496570932
246285468 496285218
244571184 494570934
744284970 244285470
743142114 243142614
243142614 493142364
742856400 242856900
242856900 49285...

output:

out
out
out
out
out
out
out
in
out
out
in
out
out
in
in
in
out
in
out
out
in
in
in
in
in
out
in
out
out
out
out
in
out
out
in
in
out
out
in
out
out
out
out
out
out
out
out
in
out
out
in
out
in
out
in
out
out
in
in
out
in
in
out
out
out
out
in
out
out
in
out
out
out
in
out
out
out
out
out
out
in
out
...

result:

ok 2500 lines

Test #2:

score: 10
Accepted
time: 56ms
memory: 6340kb

input:

1000
750000000 250000000
250000000 500000000
749000000 249000000
249000000 499000000
748000000 248000000
248000000 498000000
747000000 247000000
247000000 497000000
746000000 246000000
246000000 496000000
745000000 245000000
245000000 495000000
744000000 244000000
244000000 494000000
743000000 24300...

output:

out
out
in
in
out
out
out
in
in
in
in
in
in
out
in
out
out
in
in
out
in
out
out
in
out
out
out
out
out
in
in
out
in
in
in
out
in
out
out
in
out
in
in
out
out
in
out
out
in
in
out
in
in
out
out
out
out
out
in
in
out
out
out
in
out
in
in
out
out
out
in
out
in
out
out
in
out
in
out
out
out
out
out
out
...

result:

ok 50000 lines

Test #3:

score: 10
Accepted
time: 326ms
memory: 63948kb

input:

50000
750000000 250000000
250000000 500000000
749980000 249980000
249980000 499980000
749960000 249960000
249960000 499960000
749940000 249940000
249940000 499940000
749920000 249920000
249920000 499920000
749900000 249900000
249900000 499900000
749880000 249880000
249880000 499880000
749860000 2498...

output:

out
in
out
out
in
out
in
in
in
out
out
in
out
in
out
in
in
out
in
in
out
in
out
out
out
out
out
in
in
in
in
out
in
out
out
in
in
out
out
out
out
in
out
in
out
out
out
in
out
out
out
out
out
in
in
out
out
in
in
in
out
out
out
out
in
in
out
out
in
in
in
out
in
out
out
out
out
out
out
out
out
in
in
in
...

result:

ok 50000 lines

Test #4:

score: 10
Accepted
time: 335ms
memory: 64224kb

input:

50000
750000000 250000000
250000000 500000000
749980000 249980000
249980000 499980000
749960000 249960000
249960000 499960000
749940000 249940000
249940000 499940000
749920000 249920000
249920000 499920000
749900000 249900000
249900000 499900000
749880000 249880000
249880000 499880000
749860000 2498...

output:

out
in
in
out
in
in
out
in
in
out
in
in
out
in
out
out
out
out
in
out
out
in
out
out
in
out
out
out
in
in
out
in
in
out
in
in
in
out
in
out
in
in
in
in
in
out
out
out
in
out
out
in
out
in
in
in
in
in
in
out
out
in
in
out
out
out
in
in
out
out
in
in
out
out
out
in
out
out
in
out
out
out
out
in
in
in
...

result:

ok 50000 lines

Test #5:

score: 10
Accepted
time: 517ms
memory: 95820kb

input:

50000
749981250 249993750
249993750 499987500
749967917 249980417
749954584 249967084
249967084 499960834
749927918 249940418
249927085 499920835
249913752 499907502
749887919 249900419
249900419 499894169
749874586 249887086
249887086 499880836
749861253 249873753
249873753 499867503
749847920 2498...

output:

in
out
out
in
out
out
out
out
out
in
in
out
out
out
in
in
out
out
out
out
in
in
in
in
out
in
in
out
in
out
in
out
out
in
out
out
out
in
out
out
out
out
in
in
out
out
in
out
in
in
in
out
in
in
out
out
in
out
out
in
out
in
out
out
out
in
out
out
out
in
out
out
out
out
out
out
out
out
out
out
out
out
o...

result:

ok 25000 lines

Test #6:

score: 0
Runtime Error

input:

50000
0 0
74496700 7500
73796500 33900
5672300 35100
77013100 47100
50769200 52200
65617000 53100
91964500 71600
44143900 76800
39480100 95400
46194100 98100
80769600 116700
98969300 125200
27790300 135200
48567200 145100
74787100 145100
98686700 158600
91785600 181400
52810500 196200
56393700 19950...

output:


result:


Test #7:

score: 0
Runtime Error

input:

50000
0 0
95713700 27800
99730700 29800
88466800 65800
4135700 80200
65198700 85300
38928200 87600
23872600 92400
99301400 99300
77706200 103200
50497200 141400
7153800 154400
90700400 156500
63773100 202800
84710800 216500
29457400 246600
57251000 265300
33970800 281200
87899600 286200
66693900 287...

output:


result:


Test #8:

score: 10
Accepted
time: 506ms
memory: 95768kb

input:

50000
249993750 499987500
749967917 249980417
249980417 499974167
249967084 499960834
749941251 249953751
249953751 499947501
749927918 249940418
749914585 249927085
249927085 499920835
749901252 249913752
749874586 249887086
249887086 499880836
749861253 249873753
249873753 499867503
749834587 2498...

output:

out
out
out
out
out
out
out
out
out
out
in
in
out
out
in
out
out
out
out
out
out
out
out
in
in
out
out
out
out
in
in
out
out
out
out
out
out
out
out
in
out
out
in
out
in
out
out
out
out
in
out
out
in
in
out
out
out
out
out
out
out
out
in
out
out
out
in
out
out
out
out
out
out
out
out
in
in
out
out
o...

result:

ok 25000 lines

Test #9:

score: 10
Accepted
time: 515ms
memory: 96064kb

input:

50000
749981250 249993750
249993750 499987500
749967917 249980417
249980417 499974167
749954584 249967084
249953751 499947501
749927918 249940418
249927085 499920835
249913752 499907502
749887919 249900419
249900419 499894169
749874586 249887086
749861253 249873753
249873753 499867503
749847920 2498...

output:

in
out
out
out
out
out
out
out
out
out
out
out
out
in
in
out
out
out
out
out
out
in
out
out
in
out
in
out
in
in
out
out
out
in
out
in
in
in
out
out
out
out
out
out
out
in
out
out
out
out
in
out
out
out
out
out
out
in
out
out
out
out
out
out
in
in
out
in
out
out
out
in
out
out
in
in
out
out
in
out
ou...

result:

ok 25000 lines

Test #10:

score: 10
Accepted
time: 504ms
memory: 95772kb

input:

50000
749981250 249993750
249993750 499987500
749967917 249980417
249980417 499974167
749954584 249967084
749941251 249953751
249940418 499934168
249927085 499920835
749901252 249913752
249900419 499894169
749861253 249873753
249873753 499867503
749847920 249860420
249860420 499854170
749834587 2498...

output:

out
in
out
out
in
out
out
in
in
out
in
out
in
out
out
out
in
out
in
out
out
in
out
out
out
out
in
in
in
in
out
in
out
out
out
in
in
out
in
in
in
in
out
out
out
in
out
out
out
in
in
in
in
out
in
out
in
out
out
out
out
out
out
in
in
in
in
in
out
in
in
in
out
in
out
in
out
out
out
out
out
out
out
out
o...

result:

ok 25000 lines