QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#85132 | #4817. Half Plane | Scintilla | WA | 365ms | 63520kb | C++14 | 9.8kb | 2023-03-07 00:04:24 | 2023-03-07 00:04:26 |
Judging History
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> ord;
rep(i, l, r) ord.pb(i);
sort(ord.begin(), ord.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(ord, 0, len - 1);
rep(i, 0, len - 1) {
key[ord[i]] = rng() % (1 << 30);
pre[ord[i]] = i ? pre[ord[i - 1]] : 0;
if (op[ord[i]].l.b < 0) pre[ord[i]] ^= key[ord[i]];
ord.pb(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 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)];
}
// 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);
// 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: 11ms
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: 8ms
memory: 62316kb
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
Wrong Answer
time: 365ms
memory: 63520kb
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:
359553185 280395613 376286948 670028763 149840472 622798111 207909402 773827650 310038621 376789167 815248501 937664418 289084516 448522687 884169194 442334237 303300126 338724190 816694303 479720568 651234306 651804583 661583787 429135453 459053328 568038903 965277763 883644818 462289617 95281548 1...
result:
wrong answer 1st lines differ - expected: '538200103 176562537 786040129', found: '359553185 280395613 376286948'