QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#352030 | #297. 里面还是外面 | debgxh | 80 | 517ms | 96064kb | C++20 | 5.1kb | 2024-03-12 19:45:20 | 2024-03-12 19:45:29 |
Judging History
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