QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#339656#8163. 正方形扩展Yuics75 308ms43528kbC++202.7kb2024-02-27 18:59:032024-02-27 18:59:03

Judging History

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

  • [2024-02-27 18:59:03]
  • 评测
  • 测评结果:75
  • 用时:308ms
  • 内存:43528kb
  • [2024-02-27 18:59:03]
  • 提交

answer

#include <bits/stdc++.h>

#define int long long

constexpr int N = 1e6 + 7;
constexpr int inf = 1e18;

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;
}

signed 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);
	
	/* 预处理 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];
		}
	}

	Max = -inf, Min = inf;
	
	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: 9828kb

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

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

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

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

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

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

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

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

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

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

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: 34ms
memory: 15960kb

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: 30ms
memory: 11860kb

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: 30ms
memory: 13888kb

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: 35ms
memory: 12608kb

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: 296ms
memory: 43524kb

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: 294ms
memory: 43260kb

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: 285ms
memory: 43268kb

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: 290ms
memory: 43528kb

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: 308ms
memory: 43304kb

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'