QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#48083#2559. Endless RoadPure_FuriesWA 438ms872972kbC++6.4kb2022-09-11 15:59:382022-09-11 15:59:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-11 15:59:39]
  • 评测
  • 测评结果：WA
  • 用时：438ms
  • 内存：872972kb
查看
  • [2022-09-11 15:59:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,l[250003],r[250003];
namespace seg1{
	int dat[1048576],tag[1048576],val[1048576];
	void pushdown(int k){
		if(tag[k]){
			tag[k<<1]=tag[k];
			dat[k<<1]=0;
			tag[k<<1|1]=tag[k];
			dat[k<<1|1]=0; 
		}
	}
	void pushup(int k){
		dat[k]=dat[k<<1]+dat[k<<1|1];
	}
	void modify(int l,int r,int _l,int _r,int k){
		if(_l<=l&&r<=_r){
			dat[k]=0;
			tag[k]=1;
			return;
		}
		if(l>_r||r<_l)return;
		pushdown(k);
		modify(l,l+r>>1,_l,_r,k<<1);
		modify(l+r+1>>1,r,_l,_r,k<<1|1);
		pushup(k);
	}
	int query(int l,int r,int _l,int _r,int k){
		if(_l<=l&&r<=_r)
			return dat[k];
		if(l>_r||r<_l)
			return 0;
		pushdown(k);
		int ret=query(l,l+r>>1,_l,_r,k<<1)+query(l+r+1>>1,r,_l,_r,k<<1|1);
		pushup(k); 
		return ret;
	}
	unordered_map<int,int>mp;
	deque<int>v;
	void build(int k,int l,int r){
		dat[k]=v[r+1]-v[l];
		if(l==r)return;
		build(k<<1,l,l+r>>1);
		build(k<<1|1,l+r+1>>1,r);
	}
	bool vis[5003];
	int Val[10003],sum[10003];
	void init(){
		for(int i=0;i<n;i++)
			v.push_back(l[i]),
			v.push_back(r[i]);
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
		while(v.size()<=524288)
			v.push_back(v.back()+1);
		for(int i=0;i<v.size();i++)
			mp[v[i]]=i;
		if(n<=5000){
			for(int i=0;i<n;i++)
				l[i]=mp[l[i]],
				r[i]=mp[r[i]];
			for(int i=1;i<n+n;i++)
				Val[i]=v[i]-v[i-1];
			for(int i=0;i<n;i++){
				for(int j=0;j<n+n;j++)
					sum[j]=(j?sum[j-1]:0)+Val[j];
				pair<int,int>nw={1073741823,-1};
				for(int j=0;j<n;j++)
					if(!vis[j])
						nw=min(nw,{sum[r[j]]-sum[l[j]],j});
				int k=nw.second;
				vis[k]=1;
				for(int j=l[k]+1;j<=r[k];j++)
					Val[j]=0;
				printf("%d ",k+1);
			}exit(0);
		}
		build(1,0,524287);
	}
}
namespace seg2{
	pair<int,int>dat[524288];
	queue<pair<int,int> >v[524288];
	void init(){
		for(int i=0;i<524288;i++)
			dat[i]={1073741823,-1};
	}
	inline void pushup(int k){
		dat[k]=min(dat[k<<1],dat[k<<1|1]);
	}
	void change(int k,pair<int,int>val){
		k+=262144;
		if(val.second<0)
			v[k].pop();
		else
			v[k].push(val);
		if(v[k].size()==0)
			dat[k]={1073741823,-1};
		else
			dat[k]=v[k].front();
		k>>=1;
		while(k){
			pushup(k);
			k>>=1;
		}
	}
	inline pair<int,int>query(int _l,int _r,int l,int r,int k){
		if(l>_r||r<_l)return {1073741823,-1};
		if(l<=_l&&_r<=r)return dat[k];
		return min(query(_l,_l+_r>>1,l,r,k<<1),query(_l+_r+1>>1,_r,l,r,k<<1|1));
	}
}
namespace seg3{
	pair<int,int>dat[524288];
	queue<pair<int,int> >v[524288];
	void init(){
		for(int i=0;i<524288;i++)
			dat[i]={1073741823,-1};
	}
	inline void pushup(int k){
		dat[k]=min(dat[k<<1],dat[k<<1|1]);
	}
	void change(int k,pair<int,int>val){
		k+=262144;
		if(val.second<0)
			v[k].pop();
		else
			v[k].push(val);
		if(v[k].size()==0)
			dat[k]={1073741823,-1};
		else
			dat[k]=v[k].front();
		k>>=1;
		while(k){
			pushup(k);
			k>>=1;
		}
	}
	inline pair<int,int>query(int _l,int _r,int l,int r,int k){
		if(l>_r||r<_l)return {1073741823,-1};
		if(l<=_l&&_r<=r)return dat[k];
		return min(query(_l,_l+_r>>1,l,r,k<<1),query(_l+_r+1>>1,_r,l,r,k<<1|1));
	}
}
namespace seg4{
	int nxt[2][2][8000003],N;
	pair<int,int>dat[8000003];
	int lzy[8000003]; 
	void init(){
		memset(nxt,-1,sizeof(nxt));
	}
	inline void pushup(int k){
		dat[k].first=1073741823;
		if(nxt[0][0][k]!=-1)dat[k]=min(dat[nxt[0][0][k]],dat[k]);
		if(nxt[0][1][k]!=-1)dat[k]=min(dat[nxt[0][1][k]],dat[k]);
		if(nxt[1][0][k]!=-1)dat[k]=min(dat[nxt[1][0][k]],dat[k]);
		if(nxt[1][1][k]!=-1)dat[k]=min(dat[nxt[1][1][k]],dat[k]);
	}
	inline void pushdown(int k){
		if(nxt[0][0][k]!=-1)lzy[nxt[0][0][k]]+=lzy[k],dat[nxt[0][0][k]].first+=lzy[k];
		if(nxt[0][1][k]!=-1)lzy[nxt[0][1][k]]+=lzy[k],dat[nxt[0][1][k]].first+=lzy[k];
		if(nxt[1][0][k]!=-1)lzy[nxt[1][0][k]]+=lzy[k],dat[nxt[1][0][k]].first+=lzy[k];
		if(nxt[1][1][k]!=-1)lzy[nxt[1][1][k]]+=lzy[k],dat[nxt[1][1][k]].first+=lzy[k];
		lzy[k]=0;
	}
	inline int change(int _lx,int _rx,int _ly,int _ry,int x,int y,int k,pair<int,int>val){
		if(k==-1)
			k=++N;
		if(_lx==_rx&&_ly==_ry){
			dat[k]=val;
			return k;
		}
		pushdown(k);
		if(x<=(_lx+_rx>>1)&&y<=(_ly+_ry>>1))nxt[0][0][k]=change(_lx,_lx+_rx>>1,_ly,_ly+_ry>>1,x,y,nxt[0][0][k],val);
		if(x<=(_lx+_rx>>1)&&y>(_ly+_ry>>1))nxt[0][1][k]=change(_lx,_lx+_rx>>1,_ly+_ry+1>>1,_ry,x,y,nxt[0][1][k],val);
		if(x>(_lx+_rx>>1)&&y<=(_ly+_ry>>1))nxt[1][0][k]=change(_lx+_rx+1>>1,_rx,_ly,_ly+_ry>>1,x,y,nxt[1][0][k],val);
		if(x>(_lx+_rx>>1)&&y>(_ly+_ry>>1))nxt[1][1][k]=change(_lx+_rx+1>>1,_rx,_ly+_ry+1>>1,_ry,x,y,nxt[1][1][k],val);
		pushup(k);
		return k;
	}
	inline void add(int _lx,int _rx,int _ly,int _ry,int lx,int rx,int ly,int ry,int k,int val){
		if(k==-1||lx>_rx||rx<_lx||ly>_ry||ry<_ly)return;
		if(lx<=_lx&&_rx<=rx&&ly<=_ly&&_ry<=ry){lzy[k]+=val;dat[k].first+=val;return;}
		pushdown(k);
		add(_lx,_lx+_rx>>1,_ly,_ly+_ry>>1,lx,rx,ly,ry,nxt[0][0][k],val);
		add(_lx,_lx+_rx>>1,_ly+_ry+1>>1,_ry,lx,rx,ly,ry,nxt[0][1][k],val);
		add(_lx+_rx+1>>1,_rx,_ly,_ly+_ry>>1,lx,rx,ly,ry,nxt[1][0][k],val);
		add(_lx+_rx+1>>1,_rx,_ly+_ry+1>>1,_ry,lx,rx,ly,ry,nxt[1][1][k],val);
		pushup(k);
		return;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d%d",l+i,r+i);
	seg1::init();
	seg2::init();
	seg3::init();
	seg4::init();
	for(int i=0;i<n;i++){
		seg2::change(seg1::mp[l[i]],{r[i],i});
		seg3::change(seg1::mp[r[i]],{-l[i],i});
		seg4::change(0,1073741823,0,1073741823,l[i],r[i],0,{r[i]-l[i],i});
	}
	for(int i=0;i<n;i++){
		int nw=seg4::dat[0].second;
		printf("%d\n",nw);
		int del=seg1::query(0,524287,seg1::mp[l[nw]],seg1::mp[r[nw]]-1,1);
		seg1::modify(0,524287,seg1::mp[l[nw]],seg1::mp[r[nw]]-1,1);
		seg2::change(seg1::mp[l[nw]],{1073741823,-1});
		int newl=seg2::query(0,262143,seg1::mp[l[nw]],seg1::mp[r[nw]],1).second;
		seg3::change(seg1::mp[r[nw]],{1073741823,-1});
		int newr=seg3::query(0,262143,seg1::mp[l[nw]],seg1::mp[r[nw]],1).second;
		seg4::change(0,1073741823,0,1073741823,l[nw],r[nw],0,{1073741823,-1});
		seg4::add(0,1073741823,0,1073741823,0,l[nw],r[nw],1073741823,0,-del);
		if(newl!=-1){
			int vall=seg1::query(0,524287,seg1::mp[l[newl]],seg1::mp[r[newl]]-1,1);
			seg4::change(0,1073741823,0,1073741823,l[newl],r[newl],0,{vall,newl});
		}
		if(newr!=-1){
			int valr=seg1::query(0,524287,seg1::mp[l[newr]],seg1::mp[r[newr]]-1,1);
			seg4::change(0,1073741823,0,1073741823,l[newr],r[newr],0,{valr,newr});
		}
	}
}
源文件, 语言: C++

详细

Test #1:

score: 100
Accepted
time: 399ms
memory: 734096kb

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: 364ms
memory: 734912kb

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: 325ms
memory: 734640kb

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: 312ms
memory: 735972kb

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: 376ms
memory: 734892kb

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: 348ms
memory: 735760kb

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: 322ms
memory: 734896kb

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: 0
Accepted
time: 346ms
memory: 734936kb

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 62 64 66 67 68 70 71 73 77 80 84 85 87 88 89 91 38 54 39 40 61 79 41 74 78 82 42 76 83 93 45 63 75 47 49 59 69 51 55 72 81 90 86 95 92 94 96 97 98 99 52 56 57 100

result:

ok 100 tokens

Test #9:

score: -100
Wrong Answer
time: 438ms
memory: 872972kb

input:

10000
504758807 504763364
504735683 504763364
504735683 504807338
504507299 504807338
504507299 504809080
504428573 504809080
504428573 504842988
504407969 504842988
504407969 504925719
504242659 504925719
504242659 504982796
504192499 504982796
504192499 504988790
504164090 504988790
504164090 5049...

output:

0
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
101
10...

result:

wrong answer 1st words differ - expected: '1', found: '0'
English 繁體中文 简体中文

服务器时间: 2025-01-20 21:46:37 | 开源项目