QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#339648 | #8163. 正方形扩展 | Yuics | 75 | 293ms | 23804kb | C++20 | 2.7kb | 2024-02-27 18:50:49 | 2024-02-27 18:50:49 |
Judging History
answer
#include <bits/stdc++.h>
constexpr int N = 1e6 + 7;
constexpr int inf = 2147483647;
int n, Max, Min;
int mxn[N], mnn[N];
struct node {
int x, y, id;
} p[N];
bool flg[N];
bool cmpx(const node &a, const node &b) {
return a.x < b.x;
}
bool cmpy(const node &a, const node &b) {
return a.y < b.y;
}
void Update(int x) {
Max = std::max(Max, x);
Min = std::min(Min, x);
}
bool Check(int x, int i) {
// 挡没挡住
if (mxn[i] > x && Min <= x)
return 1;
if (mnn[i] < x && Max >= x)
return 1;
if (Max >= x && Min <= x)
return 1;
return 0;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::cin >> n;
for (int i = 1; i <= n; i++) {
std::cin >> p[i].x >> p[i].y;
p[i].id = i;
}
std::sort(p + 1, p + n + 1, cmpy);
Max = -inf, Min = inf;
/* 预处理 y 坐标相同的情况 */
for (int i = 1; i <= n; i++) {
mxn[i] = mnn[i] = p[i].x;
if (i > 1 && p[i].y == p[i - 1].y) {
mxn[i] = std::max(mxn[i], mxn[i - 1]);
mnn[i] = std::min(mnn[i], mnn[i - 1]);
}
}
for (int i = n - 1; i; i--) {
if (p[i].y == p[i + 1].y) {
mxn[i] = mxn[i + 1];
mnn[i] = mnn[i + 1];
}
}
for (int i = 1; i <= n; i++) { // 下
int l = i - 1;
while (l > 0 && p[l].y == p[i - 1].y && p[l].y != p[i].y) {
Update(p[l].x);
l--;
}
if (!Check(p[i].x, i)) {
flg[p[i].id] = 1;
}
}
Max = -inf, Min = inf;
for (int i = n - 1; i; i--) { // 上
int l = i + 1;
while (l <= n && p[l].y == p[i + 1].y && p[l].y != p[i].y) {
Update(p[l].x);
l++;
}
if (!Check(p[i].x, i)) {
flg[p[i].id] = 1;
}
}
std::sort(p + 1, p + n + 1, cmpx);
Max = -inf, Min = inf;
/* 预处理 x 坐标相同的情况 */
for (int i = 1; i <= n; i++) {
mxn[i] = mnn[i] = p[i].y;
if (i > 1 && p[i].x == p[i - 1].x) {
mxn[i] = std::max(mxn[i], mxn[i - 1]);
mnn[i] = std::min(mnn[i], mnn[i - 1]);
}
}
for (int i = n - 1; i; i--) {
if (p[i].x == p[i + 1].x) {
mxn[i] = mxn[i + 1];
mnn[i] = mnn[i + 1];
}
}
for (int i = 1; i <= n; i++) { // 左
int l = i - 1;
while (l > 0 && p[l].x == p[i - 1].x && p[l].x != p[i].x) {
Update(p[l].y);
l--;
}
if (!Check(p[i].y, i)) {
flg[p[i].id] = 1;
}
}
Max = -inf, Min = inf;
for (int i = n - 1; i; i--) { // 右
int l = i + 1;
while (l <= n && p[l].x == p[i + 1].x && p[l].x != p[i].x) {
Update(p[l].y);
l++;
}
if (!Check(p[i].y, i)) {
flg[p[i].id] = 1;
}
}
for (int i = 1; i <= n; i++) {
if (flg[i])
std::cout << "1";
else
std::cout << "0";
}
std::cout << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 1ms
memory: 7760kb
input:
93 -891195274 183636471 -764495798 865415679 -12763013 785052733 -586906564 -783958570 264238694 -707787718 -39911703 487720699 -264359136 -388581638 -274661749 -773822775 -319274230 859262853 457383014 -567613225 557167482 -307328000 6438520 -61727603 -303369172 536527866 137500832 729931239 -96076...
output:
000000000000001101000100000010000110000001101000100011000000010011000000100010000000000000100
result:
ok single line: '000000000000001101000100000010...0011000000100010000000000000100'
Test #2:
score: 5
Accepted
time: 0ms
memory: 7668kb
input:
93 425744596 -763346592 -694476255 -846041072 974561491 774923809 -628833796 346949604 680084251 425847080 -340370645 -207810000 -507694333 -23214930 848231661 -407456661 -742426590 860089268 422689263 -71942145 -72622501 906526495 -516205096 939192043 -332843201 703045092 -316913280 -766629589 -436...
output:
001000000000000100010010000001000001000010000000000000011100000000000000000000000000000000010
result:
ok single line: '001000000000000100010010000001...0000000000000000000000000000010'
Test #3:
score: 5
Accepted
time: 2ms
memory: 9808kb
input:
93 -839155673 739773620 -513632871 -717115304 -352159327 -806231080 -398927042 -798002794 362551880 387670362 -890257785 -762239316 -405639326 -952518048 506086117 350550779 168062313 460961509 623803896 -157407248 500860953 -803039754 628958543 7009497 -305576589 341573086 8013673 -437380094 631159...
output:
100001100000000000010000010010001000000000100000110000010000011000000010000000000110001110000
result:
ok single line: '100001100000000000010000010010...1000000010000000000110001110000'
Test #4:
score: 5
Accepted
time: 0ms
memory: 9720kb
input:
93 -55777784 -492614621 279725346 31489298 -774673860 -371759169 689009185 851586844 674149587 -37332918 744334607 -194648430 -947335446 939307009 85437532 -682836120 -857908486 623773734 -894873991 -108748291 -623894437 873008961 -645132142 923700083 -146158950 701994956 558615865 -870318907 575767...
output:
000100100000010010000000000010010001001000000001000000110010100010001001100000001000000000000
result:
ok single line: '000100100000010010000000000010...0010001001100000001000000000000'
Test #5:
score: 5
Accepted
time: 1ms
memory: 7764kb
input:
93 -713533592 -635454137 -770832883 708430570 -558059121 33170622 -827677587 112798996 -187786603 -539245441 508759084 -131912616 -353711409 -424317105 -511992693 223912502 561181185 55621893 440222322 -963734151 -244337570 828997042 378649757 537398508 928459822 302910613 8314637 -757107323 1801067...
output:
000000000000000010000001001000001100000000001010000100001100010000001000000100010000001100100
result:
ok single line: '000000000000000010000001001000...0000001000000100010000001100100'
Test #6:
score: 5
Accepted
time: 0ms
memory: 9720kb
input:
994 132337322 -248374937 559796267 675748149 -633466450 -282867388 635029297 935624612 -616797346 142752210 -391353093 425376030 515504409 124042066 507942567 -313960412 -521192070 255038684 90980398 -314859839 -96195922 -986991023 617383991 889877827 988360733 156745592 -2091028 -996880211 84679360...
output:
000000000000010000100000000000000000000000000010000000000000000000000000000001000000000100000000000000001000001000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000...
result:
ok single line: '000000000000010000100000000000...0000000000000000001000000000000'
Test #7:
score: 5
Accepted
time: 0ms
memory: 9832kb
input:
994 -492139010 -46669548 -882542984 275467157 -17445150 585190424 -20659660 714857300 -841720033 156484153 -960557373 -671452686 -548289280 -5116964 43623641 806769011 -927401447 -828655757 356469093 -3815548 1341969 565100061 303616682 607278643 -287784294 429697560 618866496 -572314494 158775360 9...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010001000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000001000000000000000000000...
result:
ok single line: '000000000000000000000000000000...0000000001000000000000000000000'
Test #8:
score: 5
Accepted
time: 1ms
memory: 7748kb
input:
994 -991943642 149709305 617536314 -956007912 551659965 -417294918 239320425 -866155837 -150159419 -230139607 961842983 -860054268 -3278948 94129648 30465251 -660947569 -728872863 -595955430 -698729830 -750571722 691286235 -396789172 -576267739 -369690695 526939053 -558483679 214965740 -903655097 63...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000010000000000000000011000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000001000000000001000000000000000000010000000000...
result:
ok single line: '000000000000000000000000000000...0000001000000000000000000000000'
Test #9:
score: 5
Accepted
time: 2ms
memory: 9720kb
input:
994 -378441321 814776920 -653579269 -808649251 -858046754 -850942195 635182079 50925408 572223710 109332396 667322370 -845880004 -586628398 -623420189 -529720906 -987658525 644688146 -431218952 469801275 -632471828 732133729 -97486180 -301827737 720127213 -222418892 217477782 -960714191 816193498 -4...
output:
000000000000000000000000000000000000000000000000000000010000000000000001000000000000000000000000000000000000000000000000000000000000000000001000000000000000100000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000...
result:
ok single line: '000000000000000000000000000000...0000001000000000000000000000000'
Test #10:
score: 5
Accepted
time: 1ms
memory: 7680kb
input:
994 42881277 -389747079 -303235012 -6073797 -783523239 -830498296 333505505 -854393816 -846375205 818543885 607580537 379453828 -533787033 -981507466 394476661 -564776947 841880342 -780970409 -618168322 370219284 -46908995 -432324255 -374363729 545078108 -215473580 -731825830 -111920705 -363559676 5...
output:
000000000000000000000000001000000000001000000000000000001000000000000000000000001000000010000000010000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000001100000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok single line: '000000000000000000000000001000...0000000000000000000000000000000'
Test #11:
score: 5
Accepted
time: 30ms
memory: 9996kb
input:
98000 804654485 -744589770 -390178962 -312567041 264881853 -27746749 46139687 -769193873 -644456233 573561085 -927857093 555049356 -790224658 932644261 37514057 23680949 -779103281 118117640 -790064600 -303534788 -348907291 480151426 703520670 -611052944 -372543914 762722572 684190816 -962335157 691...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #12:
score: 5
Accepted
time: 31ms
memory: 13908kb
input:
98000 -142537033 126484793 -849399359 -661325010 -839721095 -298797100 -624435193 628377831 105793747 -427252914 124599678 907914904 -799915472 -171898998 -285202012 -470716116 -539486984 438926447 298795968 -961437874 -784645661 -48144879 43931023 -359076166 887584355 401558381 -907961552 -64382875...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #13:
score: 5
Accepted
time: 29ms
memory: 10148kb
input:
98000 -244720507 -702984313 -312465875 385759510 82827306 -752248507 797979578 181094929 -824200106 -590134708 328689599 -70698588 -943542140 301758529 196851432 -885205721 -932618829 939164518 921098273 -629167679 29740313 -926390238 425409853 -595254890 585276549 137116830 290893228 -34952153 -114...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #14:
score: 5
Accepted
time: 25ms
memory: 9848kb
input:
98000 520182983 -205371799 577896599 897028924 -404975418 68868800 427787550 851260967 140225011 -794206401 44559478 831583661 660452491 -281553300 -833363315 -469397898 -604819885 -408752163 -418773145 796419534 -719242520 124812576 939078297 983229713 -937756051 -289036237 -731984828 640338913 -26...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #15:
score: 5
Accepted
time: 34ms
memory: 10688kb
input:
98000 -882511044 -154470099 830933082 -230185106 244669700 387784250 697379098 954838344 -71112753 -514336768 930483099 -50014892 440727179 -805773140 254519670 -449623387 -655915001 -293915908 -244018278 421271996 490817929 127119500 589198456 491991409 -507437303 676768295 484753403 -2648195 -7205...
output:
000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok single line: '000000000000000000000000000000...0000000000000000000000000000000'
Test #16:
score: 0
Wrong Answer
time: 285ms
memory: 23796kb
input:
999666 8754 -802 9837 7259 701 67 8422 1665 -6119 -639 -6104 6642 -6366 8931 2500 2882 5232 7673 3155 -8842 -2641 4333 -2022 3479 -341 4907 9673 5185 6640 -6820 -3562 -8458 8254 5885 6330 -6191 -8264 4113 4076 -4478 5571 -7570 -8846 -3595 -8253 2027 -9706 5515 3737 -3789 -4107 -2978 5827 -1700 6117 ...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer 1st lines differ - expected: '000000000000000000000000000000...0000000000000000000000000000000', found: '000000000000000000000000000000...0000000000000000000000000000000'
Test #17:
score: 0
Wrong Answer
time: 284ms
memory: 23804kb
input:
999666 -4210 9110 8072 -2488 -3310 -2141 -2487 -8351 -3113 -1551 -5822 6798 -2082 -9306 -5198 -808 -2509 8374 7652 -7838 8323 -247 6971 8952 415 5912 9617 -6501 -1073 -4766 1400 -1872 1639 -5417 7800 -2643 1135 -9021 5540 -2451 -2821 3768 -3137 -9344 995 9113 5865 -8614 -9116 -5664 -6784 7149 2174 -...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer 1st lines differ - expected: '000000000000000000000000000000...0000000000000000000000000000000', found: '000000000000000000000000000000...0000000000000000000000000000000'
Test #18:
score: 0
Wrong Answer
time: 293ms
memory: 23748kb
input:
999666 7017 7587 -9205 -2836 -3329 9854 7764 9690 -154 7277 9715 -5478 128 6368 -4269 116 1768 -7859 -6248 6656 3938 9073 -8521 -8565 -5253 1166 -6913 2817 1691 -4110 -7197 -7828 -7479 8746 3455 -4481 -5324 4062 3115 6388 -5881 5294 4980 6228 3565 1818 -1842 -9144 -7573 -2565 -2966 -89 5767 9771 225...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer 1st lines differ - expected: '000000000000000000000000000000...0000000000000000000000000000000', found: '000000000000000000000000000000...0000000000000000000000000000000'
Test #19:
score: 0
Wrong Answer
time: 283ms
memory: 23776kb
input:
999666 819 6794 -2354 4214 -1220 -8718 -2923 -5387 7711 -167 -34 -9371 -2002 6636 1357 7581 -176 6738 -1812 9483 -6562 908 -6127 -8376 -393 3988 -1477 4700 -3477 6920 2970 3287 1009 -3335 -1085 7488 8639 4976 -8197 8285 8208 8452 -2137 -7442 7128 6519 -8551 6382 -4745 799 -3728 -6183 5098 -4291 -902...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer 1st lines differ - expected: '000000000000000000000000000000...0000000000000000000000000000000', found: '000000000000000000000000000000...0000000000000000000000000000000'
Test #20:
score: 0
Wrong Answer
time: 285ms
memory: 23716kb
input:
999666 -8444 -2302 -6844 -5839 1533 -7807 -972 -4806 7661 -2583 -886 5534 -374 -5723 6751 2754 -4096 2322 799 6055 1083 1634 3433 8232 9297 1485 5 7732 2989 9106 4091 -3249 9344 -1154 803 -7455 769 3953 9846 -2992 6966 -7144 2929 698 9471 -9367 -3104 -4576 8570 2509 2483 7337 -1270 9369 -9792 5540 8...
output:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer 1st lines differ - expected: '000000000000000000000000000000...0000000000000000000000000000000', found: '000000000000000000000000000000...0000000000000000000000000000000'