QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55242#1962. Security SystemKING_UT#AC ✓51ms13968kbC++203.0kb2022-10-12 20:32:082022-10-12 20:32:10

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-12 20:32:10]
  • 评测
  • 测评结果:AC
  • 用时:51ms
  • 内存:13968kb
  • [2022-10-12 20:32:08]
  • 提交

answer

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

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)

#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define pb push_back
#define eb emplace_back
#define si(x) int(x.size())
template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;
using vi=vc<int>;

#define a first
#define b second
#define mp make_pair
using pi=pair<int,int>;

template<class t,class u>bool chmin(t&a,u b){
	if(a>b){
		a=b;
		return true;
	}else return false;
}
template<class t,class u>bool chmax(t&a,u b){
	if(a<b){
		a=b;
		return true;
	}else return false;
}

template<class t>void mkuni(vc<t>&vs){
	sort(all(vs));
	vs.erase(unique(all(vs)),vs.ed);
}

template<class t>int lwb(const vc<t>&vs,t v){
	return lower_bound(all(vs),v)-vs.bg;
}

const int inf=INT_MAX/2-100;

template<class t,class u>
struct slide{
	vc<t> x;
	vi y;
	u f;
	int b,e,c,d;
	slide(u ff=u()):f(ff){init();}
	void init(){b=e=c=d=0;}
	void push(t a){
		while(b<e&&f(x[e-1],a))e--;
		if(e==si(x)){
			x.eb();
			y.eb();
		}
		x[e]=a;
		y[e++]=c++;
	}
	void pop(){if(y[b]==d)b++;d++;}
	t get(){return x[b];}
	bool has(){return b<e;}
};

void slv(){
	int n;cin>>n;
	vc<pi> xy(n);
	vi xs(n);
	rep(i,n){
		cin>>xy[i].a>>xy[i].b;
		xs[i]=xy[i].a;
	}
	mkuni(xs);
	
	vc<pi> lu(si(xs)-1);
	rep(i,n){
		auto [a,b]=xy[i];
		auto [c,d]=xy[(i+1)%n];
		a=lwb(xs,a);
		c=lwb(xs,c);
		if(a<c){
			rng(j,a,c)lu[j].a=b;
		}else if(a>c){
			rng(j,c,a)lu[j].b=b;
		}
	}
	lu.erase(unique(all(lu)),lu.ed);
	int s=si(lu);
	
	vvc<pi> g(2*(s+1));
	rep(k,2)rep(i,s)g[(i+1)*2+k].eb(i*2+k,0);
	rep(i,s+1)g[i*2].eb(i*2+1,0);
	{
		vi special(s+1);iota(all(special),0);
		rep(_,2){
			int tail=s;
			per(head,s){
				if(head+2<=tail&&lu[head].a<=lu[head+1].a&&lu[head].b<=lu[head+1].b){
					while(lu[head].b<lu[tail-1].a)tail--;
				}else tail=head+1;
				if(head+2<=tail)chmax(special[head+1],tail-1);
			}
			rep(i,s){
				swap(lu[i].a,lu[i].b);
				lu[i].a*=-1;
				lu[i].b*=-1;
			}
		}
		
		vi lf(s);
		rep(i,s){
			if(i>0&&lu[i].a<=lu[i-1].a&&lu[i-1].b<=lu[i].b)
				lf[i]=lf[i-1];
			else
				lf[i]=i;
		}
		vi rt(s);
		per(i,s){
			if(i+1<s&&lu[i].a<=lu[i+1].a&&lu[i+1].b<=lu[i].b)
				rt[i]=rt[i+1];
			else
				rt[i]=i+1;
		}
		
		rep(i,s){
			int x=lf[i],y=rt[i];
			g[x*2+1].eb(y*2,1);
			g[x*2+1].eb(special[y]*2+1,1);
		}
	}
	{
		slide<int,less<int>> l;
		slide<int,greater<int>> r;
		int j=0;
		rep(i,s){
			l.push(lu[i].a);
			r.push(lu[i].b);
			while(l.get()>=r.get()){
				l.pop();
				r.pop();
				j++;
			}
			
			int x=j,y=i+1;
			g[x*2].eb(y*2,1);
		}
	}
	
	vi dist(si(g),inf);
	deque<int> q;
	auto reach=[&](int v,int d,bool f){
		if(chmin(dist[v],d)){
			if(f)q.push_front(v);
			else q.push_back(v);
		}
	};
	reach(0,0,true);
	while(si(q)){
		int v=q.front();q.pop_front();
		for(auto [to,c]:g[v])reach(to,dist[v]+c,c==0);
	}
	cout<<dist[s*2]<<endl;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	slv();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3652kb

input:

16
2 1
11 1
11 7
13 7
13 3
17 3
17 6
15 6
15 9
8 9
8 6
5 6
5 9
1 9
1 4
2 4

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

34
29 5
29 11
26 11
26 9
23 9
23 12
20 12
20 11
15 11
15 5
13 5
13 10
11 10
11 13
8 13
8 7
5 7
5 11
1 11
1 2
6 2
6 4
9 4
9 8
12 8
12 1
18 1
18 6
22 6
22 3
25 3
25 7
27 7
27 5

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

20
1 2
5 2
5 6
7 6
7 1
15 1
15 6
17 6
17 2
19 2
19 8
13 8
13 5
9 5
9 10
6 10
6 8
3 8
3 5
1 5

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3572kb

input:

20
1 2
5 2
5 5
7 5
7 1
15 1
15 5
17 5
17 2
19 2
19 8
13 8
13 5
9 5
9 10
6 10
6 8
3 8
3 5
1 5

output:

3

result:

ok single line: '3'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

8
1 3
4 3
4 1
7 1
7 6
4 6
4 8
1 8

output:

1

result:

ok single line: '1'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

12
1 1
5 1
5 4
8 4
8 6
6 6
6 9
4 9
4 7
2 7
2 3
1 3

output:

1

result:

ok single line: '1'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

12
1 1
4 1
4 4
8 4
8 6
6 6
6 9
4 9
4 7
2 7
2 3
1 3

output:

2

result:

ok single line: '2'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3744kb

input:

12
1 4
5 4
5 1
8 1
8 3
7 3
7 7
5 7
5 9
3 9
3 6
1 6

output:

2

result:

ok single line: '2'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3748kb

input:

12
1 4
4 4
4 1
8 1
8 3
7 3
7 7
5 7
5 9
3 9
3 6
1 6

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

24
20 1
20 7
18 7
18 4
16 4
16 7
12 7
12 4
9 4
9 7
5 7
5 4
3 4
3 7
1 7
1 1
6 1
6 5
8 5
8 1
13 1
13 5
15 5
15 1

output:

4

result:

ok single line: '4'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3632kb

input:

4
-1 -1
1 -1
1 1
-1 1

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

20
0 0
30 0
30 20
40 20
40 0
70 0
70 20
80 20
80 0
90 0
90 30
60 30
60 10
50 10
50 30
20 30
20 10
10 10
10 30
0 30

output:

3

result:

ok single line: '3'

Test #13:

score: 0
Accepted
time: 35ms
memory: 13968kb

input:

100000
0 0
30 0
30 20
40 20
40 0
70 0
70 20
80 20
80 0
110 0
110 20
120 20
120 0
150 0
150 20
160 20
160 0
190 0
190 20
200 20
200 0
230 0
230 20
240 20
240 0
270 0
270 20
280 20
280 0
310 0
310 20
320 20
320 0
350 0
350 20
360 20
360 0
390 0
390 20
400 20
400 0
430 0
430 20
440 20
440 0
470 0
470 2...

output:

16667

result:

ok single line: '16667'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

50
27 4
27 8
25 8
25 12
23 12
23 10
21 10
21 6
19 6
19 16
17 16
17 18
16 18
16 21
14 21
14 19
12 19
12 15
11 15
11 12
9 12
9 19
7 19
7 18
5 18
5 10
2 10
2 8
1 8
1 6
4 6
4 7
7 7
7 4
8 4
8 1
9 1
9 9
10 9
10 11
14 11
14 8
17 8
17 5
19 5
19 3
22 3
22 7
23 7
23 4

output:

4

result:

ok single line: '4'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3640kb

input:

28
7 11
5 11
5 6
3 6
3 8
1 8
1 5
13 5
13 1
15 1
15 2
18 2
18 1
20 1
20 5
19 5
19 3
17 3
17 4
16 4
16 3
14 3
14 6
11 6
11 9
9 9
9 7
7 7

output:

2

result:

ok single line: '2'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

50
31 2
31 5
30 5
30 6
28 6
28 8
26 8
26 10
22 10
22 5
20 5
20 14
18 14
18 8
16 8
16 9
15 9
15 6
13 6
13 16
7 16
7 14
3 14
3 11
1 11
1 7
4 7
4 5
6 5
6 12
8 12
8 8
10 8
10 1
12 1
12 3
13 3
13 1
15 1
15 3
17 3
17 7
19 7
19 2
24 2
24 7
26 7
26 3
29 3
29 2

output:

6

result:

ok single line: '6'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

14
-30000000 -20000000
30000000 -20000000
30000000 0
20000000 0
20000000 10000000
10000000 10000000
10000000 -10000000
0 -10000000
0 20000000
-10000000 20000000
-10000000 10000000
-20000000 10000000
-20000000 0
-30000000 0

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

36
19 2
19 8
17 8
17 6
15 6
15 10
13 10
13 5
11 5
11 8
9 8
9 5
7 5
7 10
5 10
5 6
3 6
3 8
1 8
1 1
3 1
3 5
5 5
5 2
7 2
7 4
9 4
9 2
11 2
11 4
13 4
13 2
15 2
15 5
17 5
17 2

output:

3

result:

ok single line: '3'

Test #19:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

48
1 6
2 6
2 5
3 5
3 6
5 6
5 3
8 3
8 2
9 2
9 3
12 3
12 1
15 1
15 6
16 6
16 8
20 8
20 5
22 5
22 3
23 3
23 5
25 5
25 2
28 2
28 5
27 5
27 4
26 4
26 6
24 6
24 9
23 9
23 7
22 7
22 11
18 11
18 10
17 10
17 9
14 9
14 7
10 7
10 5
7 5
7 10
1 10

output:

5

result:

ok single line: '5'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

46
1 9
3 9
3 1
8 1
8 3
13 3
13 7
15 7
15 9
17 9
17 3
18 3
18 2
19 2
19 3
21 3
21 4
22 4
22 3
24 3
24 6
25 6
25 4
26 4
26 1
30 1
30 3
28 3
28 8
25 8
25 7
23 7
23 5
20 5
20 7
18 7
18 10
14 10
14 13
11 13
11 5
8 5
8 10
6 10
6 13
1 13

output:

4

result:

ok single line: '4'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

1024
0 0
92 0
92 -49
107 -49
107 -93
200 -93
200 -107
229 -107
229 -161
269 -161
269 -218
316 -218
316 -246
389 -246
389 -269
418 -269
418 -299
514 -299
514 -355
601 -355
601 -377
688 -377
688 -396
744 -396
744 -418
849 -418
849 -432
905 -432
905 -481
918 -481
918 -492
1017 -492
1017 -538
1065 -538
...

output:

1

result:

ok single line: '1'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

80
-1 12
1 12
1 25
41 25
41 -10
43 -10
43 -8
53 -8
53 15
72 15
72 6
88 6
88 1
90 1
90 40
100 40
100 70
120 70
120 77
162 77
162 64
179 64
179 38
195 38
195 6
210 6
210 2
236 2
236 -6
238 -6
238 -2
250 -2
250 39
286 39
286 15
288 15
288 86
314 86
314 44
316 44
316 91
302 91
302 115
300 115
300 96
276...

output:

5

result:

ok single line: '5'

Test #23:

score: 0
Accepted
time: 2ms
memory: 3612kb

input:

400
-2 12
2 12
2 25
40 25
40 -10
44 -10
44 -8
54 -8
54 15
71 15
71 6
87 6
87 1
91 1
91 40
101 40
101 70
121 70
121 77
161 77
161 64
178 64
178 38
199 38
199 6
214 6
214 2
218 2
218 74
266 74
266 46
270 46
270 62
302 62
302 51
315 51
315 10
319 10
319 74
362 74
362 66
378 66
378 38
382 38
382 59
427 ...

output:

11

result:

ok single line: '11'

Test #24:

score: 0
Accepted
time: 3ms
memory: 3732kb

input:

2020
95 2322
582 2322
582 1435
592 1435
592 4400
1067 4400
1067 -98
1077 -98
1077 8325
2768 8325
2768 4616
2778 4616
2778 7611
4014 7611
4014 2550
4654 2550
4654 2080
4664 2080
4664 8987
5858 8987
5858 6974
6795 6974
6795 1648
6805 1648
6805 5148
6966 5148
6966 6895
8109 6895
8109 1904
8119 1904
811...

output:

35

result:

ok single line: '35'

Test #25:

score: 0
Accepted
time: 20ms
memory: 6276kb

input:

40000
-100005 2322
-99518 2322
-99518 1435
-99508 1435
-99508 4400
-99033 4400
-99033 -98
-99023 -98
-99023 8325
-97332 8325
-97332 4616
-97322 4616
-97322 7611
-96086 7611
-96086 2550
-95446 2550
-95446 2080
-95436 2080
-95436 8987
-94242 8987
-94242 6974
-93305 6974
-93305 1648
-93295 1648
-93295 ...

output:

723

result:

ok single line: '723'

Test #26:

score: 0
Accepted
time: 51ms
memory: 11312kb

input:

100000
-100005 2322
-99518 2322
-99518 1435
-99508 1435
-99508 4400
-99033 4400
-99033 -98
-99023 -98
-99023 8325
-97332 8325
-97332 4616
-97322 4616
-97322 7611
-96086 7611
-96086 2550
-95446 2550
-95446 2080
-95436 2080
-95436 8987
-94242 8987
-94242 6974
-93305 6974
-93305 1648
-93295 1648
-93295...

output:

1906

result:

ok single line: '1906'

Test #27:

score: 0
Accepted
time: 2ms
memory: 3716kb

input:

480
-99999905 2322
-99999418 2322
-99999418 1435
-99999408 1435
-99999408 4400
-99998933 4400
-99998933 -98
-99998923 -98
-99998923 8325
-99997232 8325
-99997232 4616
-99997222 4616
-99997222 7611
-99995986 7611
-99995986 2550
-99995346 2550
-99995346 2080
-99995336 2080
-99995336 8987
-99994142 898...

output:

12

result:

ok single line: '12'

Test #28:

score: 0
Accepted
time: 44ms
memory: 12116kb

input:

100000
-2 12
2 12
2 25
40 25
40 -10
44 -10
44 -8
54 -8
54 15
71 15
71 6
87 6
87 1
91 1
91 40
101 40
101 70
121 70
121 77
161 77
161 64
178 64
178 38
199 38
199 6
214 6
214 2
218 2
218 74
266 74
266 46
270 46
270 62
302 62
302 51
315 51
315 10
319 10
319 74
362 74
362 66
378 66
378 38
382 38
382 59
4...

output:

2624

result:

ok single line: '2624'

Test #29:

score: 0
Accepted
time: 2ms
memory: 3640kb

input:

58
1 4
3 4
3 7
5 7
5 4
6 4
6 7
7 7
7 4
8 4
8 6
11 6
11 4
12 4
12 5
14 5
14 1
15 1
15 3
17 3
17 5
18 5
18 1
19 1
19 5
20 5
20 8
22 8
22 2
23 2
23 5
27 5
27 3
29 3
29 4
28 4
28 9
27 9
27 7
24 7
24 10
17 10
17 7
16 7
16 9
14 9
14 6
13 6
13 10
10 10
10 8
9 8
9 10
4 10
4 8
2 8
2 6
1 6

output:

5

result:

ok single line: '5'

Test #30:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

16
1 1
3 1
3 4
12 4
12 8
19 8
19 10
16 10
16 12
14 12
14 14
8 14
8 9
5 9
5 7
1 7

output:

2

result:

ok single line: '2'

Test #31:

score: 0
Accepted
time: 2ms
memory: 3696kb

input:

20
1 4
4 4
4 2
5 2
5 5
6 5
6 4
8 4
8 1
10 1
10 2
11 2
11 3
9 3
9 6
7 6
7 9
2 9
2 5
1 5

output:

2

result:

ok single line: '2'

Test #32:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

20
1 4
4 4
4 2
5 2
5 6
6 6
6 4
8 4
8 1
10 1
10 2
11 2
11 3
9 3
9 6
7 6
7 9
2 9
2 5
1 5

output:

2

result:

ok single line: '2'

Test #33:

score: 0
Accepted
time: 2ms
memory: 3744kb

input:

20
1 4
4 4
4 2
5 2
5 7
6 7
6 4
8 4
8 1
10 1
10 2
11 2
11 3
9 3
9 6
7 6
7 9
2 9
2 5
1 5

output:

3

result:

ok single line: '3'

Test #34:

score: 0
Accepted
time: 2ms
memory: 3656kb

input:

22
1 4
4 4
4 2
5 2
5 6
6 6
6 5
7 5
7 4
8 4
8 1
10 1
10 2
11 2
11 3
9 3
9 6
7 6
7 9
2 9
2 5
1 5

output:

2

result:

ok single line: '2'

Test #35:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

32
1 5
2 5
2 1
7 1
7 3
9 3
9 2
10 2
10 7
11 7
11 6
13 6
13 1
15 1
15 2
16 2
16 3
14 3
14 8
12 8
12 9
8 9
8 6
6 6
6 5
5 5
5 4
4 4
4 7
3 7
3 6
1 6

output:

3

result:

ok single line: '3'

Test #36:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

24
0 80
10 80
10 50
20 50
20 40
30 40
30 20
40 20
40 10
50 10
50 0
60 0
60 20
50 20
50 30
40 30
40 60
30 60
30 70
20 70
20 100
10 100
10 90
0 90

output:

3

result:

ok single line: '3'

Test #37:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

60
1 12
1 5
2 5
2 7
5 7
5 3
7 3
7 2
9 2
9 1
10 1
10 6
13 6
13 4
14 4
14 8
17 8
17 7
19 7
19 2
20 2
20 9
25 9
25 5
26 5
26 11
28 11
28 4
29 4
29 6
31 6
31 17
30 17
30 15
28 15
28 12
26 12
26 17
23 17
23 19
22 19
22 13
18 13
18 17
17 17
17 15
14 15
14 18
13 18
13 10
10 10
10 12
9 12
9 4
6 4
6 16
5 16
...

output:

3

result:

ok single line: '3'