QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#354143 | #8315. Candy Ads | PlentyOfPenalty# | ML | 2ms | 7032kb | C++20 | 8.2kb | 2024-03-14 22:28:07 | 2024-03-14 22:28:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define cho(u, x) ((u) << 1 | (x))
const int N = 5e4 + 9, S = 300;
int n, m, w, h, bln[N], tot, tmp[N], now[N];
bool ans[N], use[N];
vector<vector<int>> G;
void myassert(int x) {
if (!x) {
cout << "assertion failed" << endl;
exit(-1);
}
}
int tim, col_tot;
vector<int> dfn, low, col, ins, stk;
void tarjan(int u) {
// fprintf(stderr, "tarjan %d[%d] => dfn=%d low=%d\n", u >> 1, u & 1, dfn[u], low[u]);
dfn[u] = low[u] = ++tim;
ins[u] = true, stk.push_back(u);
for (int v : G[u])
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (ins[v]) {
low[u] = min(low[u], dfn[v]);
}
// fprintf(stderr, "tarjan %d[%d] => dfn=%d low=%d\n", u >> 1, u & 1, dfn[u], low[u]);
if (dfn[u] == low[u]) {
++col_tot;
for (;;) {
col[stk.back()] = col_tot;
ins[stk.back()] = false;
if (u == stk.back()) break;
stk.pop_back();
}
stk.pop_back();
}
}
struct point {
int x, y;
};
struct atom {
int l, r, id;
point u;
inline bool operator<(const atom &rhs) const { return r == rhs.r ? l < rhs.l : r < rhs.r; }
} a[N];
int newnode() {
++tot;
if (G.size() <= static_cast<size_t>(tot * 2 + 10)) {
G.resize(G.size() + N);
}
return tot;
}
void addedge(int u, int v) {
// fprintf(stderr, ">>> add edge %d[%d] %d[%d] || %d %d\n", u >> 1, u & 1, v >> 1, v & 1, tot, (int)G.size());
G[u].emplace_back(v);
}
void check(int i, int j) {
if (a[i].u.x < a[j].u.x) {
if (a[i].u.x + w <= a[j].u.x) return;
} else {
if (a[j].u.x + w <= a[i].u.x) return;
}
if (a[i].u.y < a[j].u.y) {
if (a[i].u.y + h <= a[j].u.y) return;
} else {
if (a[j].u.y + h <= a[i].u.y) return;
}
addedge(cho(i, 1), cho(j, 0));
addedge(cho(j, 1), cho(i, 0));
}
int d, rt;
struct node {
int x[2], l[2], r[2], ch[2], src, nod;
bool operator<(const node &rhs) const { return x[d] < rhs.x[d]; }
} kdt[N];
inline void maintain(int u) {
kdt[u].l[0] = kdt[u].x[0];
if (kdt[u].ch[0] && kdt[kdt[u].ch[0]].l[0] < kdt[u].l[0]) kdt[u].l[0] = kdt[kdt[u].ch[0]].l[0];
if (kdt[u].ch[1] && kdt[kdt[u].ch[1]].l[0] < kdt[u].l[0]) kdt[u].l[0] = kdt[kdt[u].ch[1]].l[0];
kdt[u].l[1] = kdt[u].x[1];
if (kdt[u].ch[0] && kdt[kdt[u].ch[0]].l[1] < kdt[u].l[1]) kdt[u].l[1] = kdt[kdt[u].ch[0]].l[1];
if (kdt[u].ch[1] && kdt[kdt[u].ch[1]].l[1] < kdt[u].l[1]) kdt[u].l[1] = kdt[kdt[u].ch[1]].l[1];
kdt[u].r[0] = kdt[u].x[0];
if (kdt[u].ch[0] && kdt[kdt[u].ch[0]].r[0] > kdt[u].r[0]) kdt[u].r[0] = kdt[kdt[u].ch[0]].r[0];
if (kdt[u].ch[1] && kdt[kdt[u].ch[1]].r[0] > kdt[u].r[0]) kdt[u].r[0] = kdt[kdt[u].ch[1]].r[0];
kdt[u].r[1] = kdt[u].x[1];
if (kdt[u].ch[0] && kdt[kdt[u].ch[0]].r[1] > kdt[u].r[1]) kdt[u].r[1] = kdt[kdt[u].ch[0]].r[1];
if (kdt[u].ch[1] && kdt[kdt[u].ch[1]].r[1] > kdt[u].r[1]) kdt[u].r[1] = kdt[kdt[u].ch[1]].r[1];
}
int build(int l, int r, int k) {
if (l > r) return 0;
int mid = (l + r) >> 1;
d = k;
nth_element(kdt + l, kdt + mid, kdt + r + 1);
kdt[mid].ch[0] = build(l, mid - 1, k ^ 1);
kdt[mid].ch[1] = build(mid + 1, r, k ^ 1);
maintain(mid);
return mid;
}
void query(int u, const node &cur) {
if (cur.l[0] <= kdt[u].l[0] && cur.l[1] <= kdt[u].l[1] && kdt[u].r[0] <= cur.r[0] && kdt[u].r[1] <= cur.r[1]) {
addedge(cho(cur.src, 1), cho(kdt[u].nod, 0));
addedge(cho(kdt[u].nod, 1), cho(cur.src, 0));
return;
}
if (cur.l[0] > kdt[u].r[0] || cur.l[1] > kdt[u].r[1] || cur.r[0] < kdt[u].l[0] || cur.r[1] < kdt[u].l[1]) {
return;
}
if (use[kdt[u].src] && cur.l[0] <= kdt[u].x[0] && cur.l[1] <= kdt[u].x[1] && kdt[u].x[0] <= cur.r[0] && kdt[u].x[1] <= cur.r[1]) {
addedge(cho(cur.src, 1), cho(kdt[u].src, 0));
addedge(cho(kdt[u].src, 1), cho(cur.src, 0));
}
query(kdt[u].ch[0], cur);
query(kdt[u].ch[1], cur);
}
struct block {
int l, r;
vector<int> q;
void solve() {
// fprintf(stderr, "solve block %d %d\n", l, r);
for (int i = 1; i <= n; i++) use[i] = false;
for (int x : q) use[x] = true;
for (int i = 1; i <= n; i++) {
kdt[i].nod = newnode();
}
for (int i = 1; i <= n; i++) {
if (kdt[i].ch[0]) {
addedge(cho(kdt[i].nod, 0), cho(kdt[kdt[i].ch[0]].nod, 0));
addedge(cho(kdt[kdt[i].ch[0]].nod, 1), cho(kdt[i].nod, 1));
}
if (kdt[i].ch[1]) {
addedge(cho(kdt[i].nod, 0), cho(kdt[kdt[i].ch[1]].nod, 0));
addedge(cho(kdt[kdt[i].ch[1]].nod, 1), cho(kdt[i].nod, 1));
}
if (use[kdt[i].src]) {
addedge(cho(kdt[i].nod, 0), cho(kdt[i].src, 0));
addedge(cho(kdt[i].src, 1), cho(kdt[i].nod, 1));
}
}
node cur;
for (int i = l; i <= r; i++) {
cur.l[0] = a[i].u.x - (w - 1), cur.r[0] = a[i].u.x + (w - 1);
cur.l[1] = a[i].u.y - (h - 1), cur.r[1] = a[i].u.y + (h - 1);
cur.src = i, cur.nod = -1;
query(rt, cur);
}
}
} b[N / S + 9];
int main() {
#ifdef memset0
freopen("K.in", "r", stdin);
#endif
cin.tie(0)->sync_with_stdio(0);
vector<pair<int, int>> lim;
cin >> n >> w >> h;
for (int i = 1; i <= n; i++) {
cin >> a[i].l >> a[i].r >> a[i].u.x >> a[i].u.y;
a[i].id = i;
}
sort(a + 1, a + n + 1);
// for (int i = 1; i <= n; i++) fprintf(stderr, "a[%d] => l=%d r=%d x=%d y=%d id=%d\n", i, a[i].l, a[i].r, a[i].u.x, a[i].u.y, a[i].id);
for (int i = 1; i <= n; i++) {
now[a[i].id] = i;
}
cin >> m;
tot = n;
G.resize(n * 2 + 100);
for (int u, v, i = 1; i <= m; i++) {
cin >> u >> v;
lim.emplace_back(u, v);
u = now[u];
v = now[v];
addedge(cho(u, 0), cho(v, 1));
addedge(cho(v, 0), cho(u, 1));
}
for (int i = 1; i <= n; i++) {
kdt[i].src = i;
kdt[i].x[0] = a[i].u.x;
kdt[i].x[1] = a[i].u.y;
}
rt = build(1, n, 0);
for (int i = 1; i <= n; i++) {
bln[i] = i / S + 1;
if (!b[bln[i]].l) b[bln[i]].l = i;
b[bln[i]].r = i;
// cout << bln[i] << " \n"[i == n];
}
for (int i = 1; i <= n; i++) tmp[i] = a[i].r;
for (int ql, qr, i = 1; i <= n; i++) {
ql = lower_bound(tmp + 1, tmp + i, a[i].l) - tmp;
qr = i - 1;
if (ql <= qr) {
// fprintf(stderr, "solve [ql=%d[%d] qr=%d[%d]] i=%d\n", ql, bln[ql], qr, bln[qr], i);
if (bln[ql] == bln[qr]) {
for (int j = ql; j <= qr; j++) check(j, i);
} else {
for (int j = ql; j <= b[bln[ql]].r; j++) check(j, i);
for (int j = b[bln[qr]].l; j <= qr; j++) check(j, i);
for (int k = bln[ql] + 1; k < bln[qr]; k++) {
b[k].q.emplace_back(i);
}
}
}
}
for (int i = 1; i <= bln[n]; i++) {
b[i].solve();
}
dfn.resize((tot + 1) << 1);
low.resize((tot + 1) << 1);
col.resize((tot + 1) << 1);
ins.resize((tot + 1) << 1);
for (int i = cho(1, 0); i <= cho(tot, 1); i++)
if (!dfn[i]) {
tarjan(i);
}
for (int i = 1; i <= tot; i++)
if (col[cho(i, 0)] == col[cho(i, 1)]) {
cout << "No" << endl;
return 0;
}
cout << "Yes" << endl;
for (int i = 1; i <= n; i++) {
ans[a[i].id] = col[cho(i, 0)] > col[cho(i, 1)];
}
// for (int i = 1; i <= n; i++) cerr << col[cho(i, 0)] << " \n"[i == n];
// for (int i = 1; i <= n; i++) cerr << col[cho(i, 1)] << " \n"[i == n];
for (int i = 1; i <= n; i++) {
cout << ans[i];
}
cout << endl;
return 0;
for (int i = 1; i <= n; i++) cerr << ans[i] << " \n"[i == n];
sort(a + 1, a + n + 1, [&](const atom &u, const atom &v) { return u.id < v.id; });
for (const auto &[u, v] : lim) {
myassert(ans[u] || ans[v]);
}
for (int i = 1; i <= n; i++)
if (ans[i])
for (int j = i + 1; j <= n; j++)
if (ans[j]) {
// fprintf(stderr, ">> %d %d\n", i, j);
if (a[i].r < a[j].l) continue;
if (a[j].r < a[i].l) continue;
if (a[i].u.x < a[j].u.x) {
if (a[i].u.x + w <= a[j].u.x) continue;
} else {
if (a[j].u.x + w <= a[i].u.x) continue;
}
if (a[i].u.y < a[j].u.y) {
if (a[i].u.y + h <= a[j].u.y) continue;
} else {
if (a[j].u.y + h <= a[i].u.y) continue;
}
myassert(0);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5920kb
input:
2 2 2 1 2 1 1 2 3 2 2 1 1 2
output:
Yes 01
result:
ok accepted
Test #2:
score: 0
Accepted
time: 1ms
memory: 5644kb
input:
3 2 2 1 2 1 1 1 3 1 2 2 3 2 2 3 1 2 2 3 1 3
output:
No
result:
ok accepted
Test #3:
score: 0
Accepted
time: 0ms
memory: 5872kb
input:
10 3 3 2 3 7 10 1 3 9 6 3 5 2 1 4 5 8 9 4 7 1 7 3 4 4 4 6 8 9 5 1 3 6 7 2 5 7 4 6 9 9 9 10 9 1 6 2 8 5 9 5 10 4 5 1 3 2 10 9 9 5 8 2
output:
Yes 1010110101
result:
ok accepted
Test #4:
score: 0
Accepted
time: 1ms
memory: 5648kb
input:
10 2 4 2 5 4 8 8 10 6 3 1 3 7 3 8 10 7 9 1 2 2 6 3 6 9 2 4 7 2 10 8 9 7 4 8 9 7 1 1 2 9 8 8 2 4 6 5 1 4 6 9 9 5 6 3 6 8 8 2
output:
Yes 0101110000
result:
ok accepted
Test #5:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
10 4 3 8 9 8 8 4 5 6 8 8 9 3 2 5 7 10 6 6 7 7 9 3 5 7 3 9 10 9 4 4 7 9 2 9 10 8 2 3 5 1 8 14 8 10 10 1 1 10 6 4 2 3 9 6 8 6 5 2 9 8 1 9 10 7 1 6 10 8 3 6
output:
Yes 1011100111
result:
ok accepted
Test #6:
score: 0
Accepted
time: 2ms
memory: 6440kb
input:
100 94 194 1461 1945 694 1593 217 353 761 1920 695 982 452 599 1301 1757 662 1862 1355 1574 917 258 1253 1718 10 893 822 1112 623 748 597 925 1196 65 1277 1785 17 1368 1564 1914 1637 545 1363 1810 922 1988 1001 1251 28 156 1678 1978 185 980 1730 1823 145 1803 655 1040 981 1261 593 637 212 555 1358 1...
output:
Yes 1011101101111111010111111110110001011110111111111111011010100111101111111011111111101100111111111001
result:
ok accepted
Test #7:
score: 0
Accepted
time: 2ms
memory: 6424kb
input:
100 108 62 410 579 1353 353 82 560 288 988 32 392 1431 1904 1364 1785 1489 1395 1118 1448 301 1275 995 1149 127 1756 1607 1906 1 1907 1217 1782 291 764 616 840 1552 1006 787 1202 34 200 283 316 3 460 903 1356 822 1469 1110 1370 1144 1880 439 746 509 1376 47 344 73 1807 551 1032 280 851 612 631 262 1...
output:
Yes 0001101100011011011101110101001010101101011101101101100110101110110010110111110111101011110110010111
result:
ok accepted
Test #8:
score: 0
Accepted
time: 2ms
memory: 6440kb
input:
100 61 130 1234 1525 1544 1497 1696 1819 895 1801 1079 1222 1201 1725 1581 1827 420 1191 270 782 261 417 1620 1685 415 79 103 387 832 562 1461 1488 388 1124 1246 1726 1900 874 139 632 984 1770 708 882 1235 1378 98 432 867 560 316 863 1773 1122 782 1080 428 1748 1599 1695 590 1969 1384 1941 449 1137 ...
output:
Yes 0110011110101111101100101111101101110111111111100111111100101111111101111101101101111011101110111011
result:
ok accepted
Test #9:
score: 0
Accepted
time: 0ms
memory: 6920kb
input:
1000 46 46 650 693 297 1278 322 411 1293 527 1613 1798 1513 1514 380 440 1463 1779 220 263 1459 1937 718 777 649 81 497 672 1224 818 576 597 977 1728 199 283 827 1766 248 259 1666 1199 956 1092 142 1966 1010 1159 414 186 592 728 1781 673 403 596 1021 1607 1118 1234 1511 417 810 830 1667 1125 1304 14...
output:
Yes 11111111101101100111001111111001111010101100111101111101111100011011110011111111110001111111111111111100111111111111101111101011011101111111111011111101011111111011110011101111111101101111111110110101110011111101110111011111111111111101110111111111001110110111110101100111101111010100011111111111...
result:
ok accepted
Test #10:
score: 0
Accepted
time: 0ms
memory: 4884kb
input:
1000 36 48 1100 1171 1599 1568 1906 1917 219 455 696 718 914 1154 407 562 1599 1749 1389 1535 744 1456 1791 1979 535 1206 597 670 389 111 131 171 1760 1858 770 928 1938 1633 1481 1537 1325 440 1667 1759 1038 837 869 1001 1114 1721 1523 1590 1412 1475 205 372 620 1395 1247 1396 113 1943 163 316 1852 ...
output:
Yes 11111111110111100001011111010101111001111010110111110111011010110111001111110100110001010011111110010011011011110110100011111001111111111111111111101000101101111110111111011000111111101101111110101011111111111011101111111111111111010111011101110111010111110111110111101111011111101110010111111101...
result:
ok accepted
Test #11:
score: 0
Accepted
time: 0ms
memory: 7032kb
input:
1000 37 46 174 204 1667 729 1866 1875 1884 556 792 945 1920 927 1303 1473 1163 1341 1519 1539 503 362 62 140 1262 1450 1235 1263 1031 1966 895 1057 215 1626 1135 1208 666 998 1459 1477 1941 1671 1050 1192 60 1375 137 244 1672 1445 217 414 724 1347 1043 1200 1401 68 1331 1495 919 933 1086 1137 1341 3...
output:
Yes 01111011011011011110101110111101110111110100011101110111100011111101110010111011110100110110011101111011010111111111101011111001111101111010000111001010111110101110111011111011111011001111010111100010011110110111111111110111010111111111111111110111010111111001110010110111100111110111111110111111...
result:
ok accepted
Test #12:
score: -100
Memory Limit Exceeded
input:
50000 9 9 630 678 1889 1026 1568 1607 1637 114 732 830 1245 590 1023 1032 403 698 211 243 1531 1382 593 650 248 955 708 717 1688 1772 509 536 884 582 1798 1865 522 1714 333 390 75 1044 1494 1540 1320 1543 160 211 866 1215 1847 1906 1189 1636 154 198 1074 1193 1636 1705 227 1685 940 954 508 394 1266 ...
output:
Yes 10010010111010111111010111111000011110001111111111111110011110110111101111101110110011011110110101110011010110110111101110111111100011111011101101110011110101010111010101101011010101010110111110111101010111111101111011111101111111011110101111011111011111101111111100111101111011011101111111010011...