QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#354209#8315. Candy AdsPlentyOfPenaltyTL 16ms13432kbC++209.5kb2024-03-14 23:39:062024-03-14 23:39:06

Judging History

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

  • [2024-03-14 23:39:06]
  • 评测
  • 测评结果:TL
  • 用时:16ms
  • 内存:13432kb
  • [2024-03-14 23:39:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define cho(u, x) ((u) << 1 | (x))

const int N = 5e4 + 9, S = 2;
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, stk;
vector<char> ins;
void tarjan(int 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]);
    }
  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] \n", u >> 1, u & 1, v >> 1, v & 1);
  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);
  // fprintf(stderr, "build tree u=%d lc=%d rc=%d\n", mid, kdt[mid].ch[0], kdt[mid].ch[1]);
  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]) {
    if (kdt[u].nod) {
      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);
}

void assign(int u) {
  if (kdt[u].ch[0]) assign(kdt[u].ch[0]);
  if (kdt[u].ch[1]) assign(kdt[u].ch[1]);
  if (kdt[kdt[u].ch[0]].nod && kdt[kdt[u].ch[1]].nod) {
    kdt[u].nod = newnode();
    addedge(cho(kdt[u].nod, 0), cho(kdt[kdt[u].ch[0]].nod, 0));
    addedge(cho(kdt[kdt[u].ch[0]].nod, 1), cho(kdt[u].nod, 1));
    addedge(cho(kdt[u].nod, 0), cho(kdt[kdt[u].ch[1]].nod, 0));
    addedge(cho(kdt[kdt[u].ch[1]].nod, 1), cho(kdt[u].nod, 1));
    if (use[kdt[u].src]) {
      addedge(cho(kdt[u].nod, 0), cho(kdt[u].src, 0));
      addedge(cho(kdt[u].src, 1), cho(kdt[u].nod, 1));
    }
  } else if (kdt[kdt[u].ch[0]].nod) {
    if (kdt[kdt[u].ch[0]].nod <= n) {
      kdt[u].nod = newnode();
      addedge(cho(kdt[u].nod, 0), cho(kdt[kdt[u].ch[0]].nod, 0));
      addedge(cho(kdt[kdt[u].ch[0]].nod, 1), cho(kdt[u].nod, 1));
    } else {
      kdt[u].nod = kdt[kdt[u].ch[0]].nod;
    }
    if (use[kdt[u].src]) {
      addedge(cho(kdt[u].nod, 0), cho(kdt[u].src, 0));
      addedge(cho(kdt[u].src, 1), cho(kdt[u].nod, 1));
    }
  } else if (kdt[kdt[u].ch[1]].nod) {
    if (kdt[kdt[u].ch[0]].nod <= n) {
      kdt[u].nod = newnode();
      addedge(cho(kdt[u].nod, 0), cho(kdt[kdt[u].ch[1]].nod, 0));
      addedge(cho(kdt[kdt[u].ch[1]].nod, 1), cho(kdt[u].nod, 1));
    } else {
      kdt[u].nod = kdt[kdt[u].ch[1]].nod;
    }
    if (use[kdt[u].src]) {
      addedge(cho(kdt[u].nod, 0), cho(kdt[u].src, 0));
      addedge(cho(kdt[u].src, 1), cho(kdt[u].nod, 1));
    }
  } else {
    if (use[kdt[u].src]) {
      kdt[u].nod = kdt[u].src;
    } else {
      kdt[u].nod = 0;
    }
  }
  // fprintf(stderr, "assign %d use=%d src=%d nod=%d\n", u, use[kdt[u].src], kdt[u].src, kdt[u].nod);
}

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;
    assign(rt);
    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);
  // freopen("K-big.txt", "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(tot * 2 + N);
  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();
  }
#ifdef memset0
  int edg = 0;
  for (int i = cho(1, 0); i <= cho(tot, 1); i++) edg += G[i].size();
  cerr << "tot = " << tot << "; edg = " << edg << endl;
#endif

  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];
#ifdef ONLINE_JUDGE
  for (int i = 1; i <= n; i++) cout << ans[i];
  cout << endl;
#endif

  // 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: 1ms
memory: 5180kb

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: 2ms
memory: 5164kb

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: 1ms
memory: 5188kb

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: 5232kb

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: 2ms
memory: 5184kb

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: 0ms
memory: 5480kb

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: 5212kb

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: 0ms
memory: 5196kb

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: 16ms
memory: 13432kb

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: 10ms
memory: 13380kb

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: 12ms
memory: 13392kb

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
Time 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:


result: