QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#30512#2559. Endless RoadY25tWA 18ms61080kbC++203.1kb2022-04-29 16:34:102022-04-29 16:34:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 16:34:11]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:61080kb
  • [2022-04-29 16:34:10]
  • 提交

answer

#include<bits/stdc++.h>
#define N 500005

int n,a[N],b[N];

std::map<int,int> vl,vr;
int val[N],tot;
inline int L(int x){
	return vl[val[x]];
}
inline int R(int x){
	return vr[val[x]];
}

int T[N];
inline int lb(int x){
	return x&-x;
}
inline void add(int x,int d){
	for(;x<tot;x+=lb(x))
		T[x]+=d;
}
inline int sum(int x){
	int res=0;
	for(x--;x;x-=lb(x))
		res+=T[x];
	return res;
}

int f[N];
inline int fnd(int x){
	return f[x]?f[x]=fnd(f[x]):x;
}
inline void del(int i){
	for(int x=fnd(a[i]);x<b[i];x=fnd(x))
		add(x,-(val[x+1]-val[x])),f[x]=fnd(x+1);
}
inline int len(int i){
	return sum(b[i])-sum(a[i]);
}

struct sq{
	int xl,xr,yl,yr;
	sq(int x=0,int y=0,int z=0,int w=0){
		xl=x,xr=y,yl=z,yr=w;
	}
};
struct node{
	int mn,mxl,mnr;
	node(int x=0,int y=0,int z=0){
		mn=x,mxl=y,mnr=z;
	}
};
node operator + (node x,node y){
	if(!x.mn||!y.mn)
		return x.mn?x:y;
	return node(std::min(x.mn,y.mn),a[x.mxl]>a[y.mxl]?x.mxl:y.mxl,b[x.mnr]<b[y.mnr]?x.mnr:y.mnr);
}
struct tr{
	sq s;
	node x;
};

tr t[N<<2];
inline void build(int p,std::vector<int> V,int o){
	if((int)V.size()==1){
		int i=V.back();
		t[p].s=sq(a[i],a[i],b[i],b[i]);
		t[p].x=node(i,i,i);
		return;
	}
	int mid=V.size()>>1;
	std::nth_element(V.begin(),V.begin()+mid,V.end(),[&](int i,int j){
		return o?a[i]<a[j]:b[i]<b[j];
	});
	build(p<<1,std::vector<int>(V.begin(),V.begin()+mid),o^1);
	build(p<<1|1,std::vector<int>(V.begin()+mid,V.end()),o^1);
	auto uni=[&](sq x,sq y)->sq{
		return {std::min(x.xl,y.xl),std::max(x.xr,y.xr),
				std::min(x.yl,y.yl),std::max(x.yr,y.yr)};
	};
	t[p].s=uni(t[p<<1].s,t[p<<1|1].s);
	t[p].x=t[p<<1].x+t[p<<1|1].x;
}
inline void ers(int p,int x,int y){
	if(x<t[p].s.xl||x>t[p].s.xr||y<t[p].s.yl||y>t[p].s.yr)
		return;
	if(t[p].s.xl==t[p].s.xr&&t[p].s.yl==t[p].s.yr)
		return t[p].x=node(),void();
	ers(p<<1,x,y),ers(p<<1|1,x,y);
	t[p].x=t[p<<1].x+t[p<<1|1].x;
}
inline node sum(int p,sq s){
	if(t[p].s.xl>s.xr||t[p].s.xr<s.xl||t[p].s.yl>s.yr||t[p].s.yr<s.yl)
		return node();
	if(s.xl<=t[p].s.xl&&t[p].s.xr<=s.xr&&s.yl<=t[p].s.yl&&t[p].s.yr<=s.yr)
		return t[p].x;
	return sum(p<<1,s)+sum(p<<1|1,s);
}

#define pii std::pair<int,int>
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> q;
bool vis[N];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b[i]);
		vl[a[i]]++,vl[b[i]]++;
	}
	for(auto &[x,y]:vl){
		while(y--)
			val[++tot]=x;
		y=tot;
	}
	vr=vl;
	for(int i=1;i<=n;i++)
		a[i]=vl[a[i]]--,b[i]=vl[b[i]]--;
	for(int i=1;i<tot;i++)
		add(i,val[i+1]-val[i]);
	std::vector<int> V(n);
	std::iota(V.begin(),V.end(),1);
	build(1,V,0);
	for(int i=1;i<=n;i++)
		q.emplace(len(i),i);
	while(q.size()){
		int x=q.top().second;
		q.pop();
		if(vis[x])
			continue;
		printf("%d ",x);
		vis[x]=1,del(x),ers(1,a[x],b[x]);
		int y=sum(1,sq(1,L(a[x])-1,R(b[x])+1,tot)).mn;
		if(y)
			q.emplace(len(y),y);
		y=sum(1,sq(1,R(a[x]),1,R(b[x]))).mxl;
		if(y)
			q.emplace(len(y),y);
		y=sum(1,sq(L(a[x]),tot,L(b[x]),tot)).mnr;
		if(y)
			q.emplace(len(y),y);
	}
	puts("");
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 60604kb

input:

6
1 2
2 3
3 4
4 5
1 3
3 5

output:

1 2 5 3 4 6 

result:

ok 6 tokens

Test #2:

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

input:

4
3 7
10 14
1 6
6 11

output:

1 3 2 4 

result:

ok 4 tokens

Test #3:

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

input:

100
50 51
49 51
49 52
48 52
48 53
47 53
47 54
46 54
46 55
45 55
45 56
44 56
44 57
43 57
43 58
42 58
42 59
41 59
41 60
40 60
40 61
39 61
39 62
38 62
38 63
37 63
37 64
36 64
36 65
35 65
35 66
34 66
34 67
33 67
33 68
32 68
32 69
31 69
31 70
30 70
30 71
29 71
29 72
28 72
28 73
27 73
27 74
26 74
26 75
25...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 

result:

ok 100 tokens

Test #4:

score: 0
Accepted
time: 8ms
memory: 61080kb

input:

100
41 42
99 100
47 48
50 51
56 57
61 62
27 28
85 86
44 45
3 4
26 27
20 21
92 93
33 34
86 87
69 70
84 85
62 63
81 82
2 3
13 14
32 33
82 83
70 71
46 47
45 46
19 20
83 84
57 59
63 65
59 61
82 84
45 47
48 50
70 72
42 44
84 86
26 28
61 63
2 4
17 19
65 67
54 56
67 69
96 99
42 45
47 50
34 37
14 17
51 54
7...

output:

1 2 3 4 5 6 7 8 9 10 11 38 12 13 14 15 16 17 37 18 39 19 20 40 21 22 23 24 25 26 33 27 28 32 35 29 30 31 57 73 34 47 71 36 46 41 53 42 58 43 54 44 52 77 45 63 48 62 49 64 80 50 60 79 91 51 66 89 55 65 83 56 59 67 86 61 72 82 90 96 68 75 81 93 69 74 84 92 70 87 88 94 97 99 76 78 85 95 98 100 

result:

ok 100 tokens

Test #5:

score: 0
Accepted
time: 12ms
memory: 60672kb

input:

100
26 27
68 69
33 34
96 97
42 43
6 7
60 61
22 23
9 10
19 20
38 39
7 8
73 74
64 65
53 54
84 85
15 16
79 80
62 63
11 12
32 33
80 81
95 96
54 55
83 84
89 90
55 56
74 75
97 98
81 82
23 24
57 58
14 15
34 35
59 60
40 41
46 47
18 19
21 22
56 57
35 36
69 70
82 83
94 95
63 64
86 87
31 32
76 77
39 40
47 48
4...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 

result:

ok 100 tokens

Test #6:

score: 0
Accepted
time: 12ms
memory: 60596kb

input:

100
66 67
42 43
32 33
28 29
96 97
19 20
41 42
38 39
73 74
50 51
31 32
40 41
3 4
72 73
29 30
45 46
14 15
11 12
68 69
21 22
25 26
51 52
75 76
76 77
8 9
99 100
53 54
27 28
61 62
26 27
74 75
84 85
64 65
79 80
71 72
85 86
33 34
0 1
90 91
24 25
4 6
51 53
64 66
34 36
94 96
66 68
97 99
31 33
80 82
19 21
88 ...

output:

1 2 3 4 5 6 7 8 9 10 11 48 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 76 81 31 66 32 33 34 35 36 59 37 38 39 40 42 43 46 50 55 57 64 41 44 62 74 78 87 90 45 71 47 49 51 69 52 53 54 82 56 58 72 60 68 73 61 63 91 65 75 67 70 84 94 95 77 79 88 96 98 80 89 83 85 86 92 93 97 99 100 

result:

ok 100 tokens

Test #7:

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

input:

100
69 70
15 16
55 56
91 92
34 35
92 93
20 21
10 11
22 23
4 5
82 83
86 87
77 78
49 50
65 66
29 30
83 84
1 2
13 14
30 31
32 33
0 1
19 20
48 49
31 33
87 89
8 10
92 94
54 56
21 23
57 59
51 53
1 3
83 85
77 79
63 65
31 34
46 49
7 10
80 83
24 27
91 94
74 77
66 69
51 54
77 80
20 23
56 59
34 37
43 46
87 90
...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 28 42 29 30 47 33 34 35 37 46 55 26 51 59 61 68 27 39 56 63 69 71 31 48 32 45 36 38 40 65 78 49 54 62 74 77 73 76 41 64 79 43 44 58 66 50 52 67 60 72 53 57 70 75 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 

result:

ok 100 tokens

Test #8:

score: -100
Wrong Answer
time: 18ms
memory: 60524kb

input:

100
27 28
56 57
79 80
34 35
98 99
31 32
55 56
67 68
25 26
47 48
58 59
46 47
49 50
42 43
80 81
43 44
83 84
90 91
48 49
82 83
59 60
81 82
92 93
91 92
69 70
30 31
77 78
66 67
50 51
54 55
63 64
57 58
26 27
28 29
11 12
68 70
26 28
35 37
44 46
74 76
87 89
93 95
10 12
83 85
32 34
97 99
37 39
28 30
64 66
76...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 37 34 35 36 43 44 46 48 65 50 53 58 60 67 38 54 39 40 61 79 41 74 78 82 42 45 63 75 47 49 59 69 51 55 72 81 90 62 68 64 66 70 76 83 93 71 73 77 80 84 85 86 95 87 88 89 91 52 92 94 97 96 98 99 56 57 100 

result:

wrong answer 47th words differ - expected: '62', found: '67'