QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#618405#2559. Endless RoadOthersWA 10ms76228kbC++146.0kb2024-10-06 21:48:462024-10-06 21:48:50

Judging History

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

  • [2024-10-06 21:48:50]
  • 评测
  • 测评结果：WA
  • 用时：10ms
  • 内存：76228kb
查看
  • [2024-10-06 21:48:46]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define wr(x,ch) write(x),putchar(ch)
using namespace std;
typedef pair<int,int> pai;
#define x first
#define y second
ll read() {
	ll x=0;bool f=0;char c=getchar();
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return f?-x:x;
}
void write(ll x) {
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10^48);
	return ;
}
const int N=5e5,inf=0x7f7f7f7f;
int flag[N],bit[N],top,n,lst[N],nxt[N];
set<int> st;
struct rg {
	int l,r,i;
	bool operator<(const rg &p) const {
		return r<p.r||(r==p.r&&(l>p.l||(l==p.l&&i<p.i)));
	}
}a[N];
struct node {
	int Maxl,tag;
	pai Minl,Mins;
	int Mr,Ml;
}tr[N<<2];
pai operator+(const pai &x,const pai &y) {
	if(x.x==y.x) return a[x.y].i<a[y.y].i?x:y;
	return min(x,y);
}
pai operator*(const pai &x,const pai &y) {
	if(x.x==y.x) return a[x.y].i<a[y.y].i?x:y;
	return max(x,y);
}
void update(int p,int t) {
	tr[p].Mins.x+=t;
	tr[p].tag+=t;
	return ;
}
void pushdown(int p) {
	if(tr[p].tag) update(p<<1,tr[p].tag),update(p<<1|1,tr[p].tag),tr[p].tag=0;
	return ;
}
void pushup(int p) {
	tr[p].Maxl=max(tr[p<<1].Maxl,tr[p<<1|1].Maxl);
	tr[p].Minl=tr[p<<1].Minl*tr[p<<1|1].Minl;
	tr[p].Mins=tr[p<<1].Mins+tr[p<<1|1].Mins;
	tr[p].Mr=max(tr[p<<1].Mr,tr[p<<1|1].Mr);
	tr[p].Ml=min(tr[p<<1].Ml,tr[p<<1|1].Ml);
	return ;
}
void build(int l,int r,int p,int lst) {
	if(l==r) {
		if(a[l].l>=lst) {
//			printf("%d ",l);
			tr[p].Mins=pai(flag[a[l].r]-flag[a[l].l],l);
			tr[p].Maxl=a[l].l;
			tr[p].Minl=pai(-1,0);
			tr[p].Mr=a[l].r-1;
			tr[p].Ml=a[l].l;
		}else {
			tr[p].Mins=pai(inf,0);
			tr[p].Minl=pai(a[l].l,l);
			tr[p].Maxl=0;
			tr[p].Mr=0;
			tr[p].Ml=inf;
		}
		return ;
	}
	int mid=l+r>>1;
	build(l,mid,p<<1,lst),build(mid+1,r,p<<1|1,max(lst,tr[p<<1].Maxl));
	return pushup(p);
}
void add(int x,int y) {
	while(x<=top) bit[x]+=y,x+=(x&-x);
	return ;
}
int ask(int x) {
	int tot=0;
	while(x) tot+=bit[x],x-=(x&-x);
	return tot;
}
int askl(int l,int r,int p,int lim) {
	if(tr[p].Mr<lim) return -1;
	if(l==r) return l;
	int mid=l+r>>1,ans;
	if((ans=askl(l,mid,p<<1,lim))!=-1) return ans;
	return askl(mid+1,r,p<<1|1,lim);
}
int askr(int l,int r,int p,int lim) {
	if(tr[p].Ml>lim) return -1;
	if(l==r) return l;
	int mid=l+r>>1,ans;
	if((ans=askr(mid+1,r,p<<1|1,lim))!=-1) return ans;
	return askr(l,mid,p<<1,lim);
}
void add(int s,int t,int l,int r,int p,int d) {
	if(s>t) return ;
	if(s<=l&&r<=t) return update(p,-d);
	int mid=l+r>>1;pushdown(p);
	if(s<=mid) add(s,t,l,mid,p<<1,d);
	if(t>mid) add(s,t,mid+1,r,p<<1|1,d);
	return pushup(p);
}
void deal(int x) {
	int l=askl(1,n,1,x),r=askr(1,n,1,x);
	add(l,r,1,n,1,flag[x+1]-flag[x]);
	add(x,flag[x+1]-flag[x]);
	return ;
}
int ask1(int s,int t,int l,int r,int p) {
	if(s>t) return 0;
	if(s<=l&&r<=t) return tr[p].Maxl;
	int mid=l+r>>1,ans=0;
	if(s<=mid) ans=max(ans,ask1(s,t,l,mid,p<<1));
	if(t>mid) ans=max(ans,ask1(s,t,mid+1,r,p<<1|1));
	return ans;
}
int ask3(int s,int t,int l,int r,int p) {
	if(s>t||!tr[p].Mins.y) return t+1;
	if(s<=l&&r<=t) {
		if(l==r) return l;
		int mid=l+r>>1,tmp=ask3(s,t,l,mid,p<<1);
		if(tmp!=t+1) return tmp;
		return ask3(s,t,mid+1,r,p<<1|1);
	}
	int mid=l+r>>1,tmp;
	if(s<=mid) {
		tmp=ask3(s,t,l,mid,p<<1);
		if(tmp!=t+1) return tmp;
	}
	return ask3(s,t,mid+1,r,p<<1|1);
}
pai ask2(int s,int t,int l,int r,int p) {
	if(s>t) return pai(-1,0);
	if(s<=l&&r<=t) return tr[p].Minl;
	int mid=l+r>>1;
	pai ans=pai(-1,0);
	if(s<=mid) ans=ans*ask2(s,t,l,mid,p<<1);
	if(t>mid) ans=ans*ask2(s,t,mid+1,r,p<<1|1);
	return ans;
}
void del(int x,int l,int r,int p) {
	if(l==r) {
		tr[p].Mins=pai(inf,0);
		tr[p].Minl=pai(-1,0);
		tr[p].tag=0;
		tr[p].Maxl=0;
		tr[p].Mr=0;
		tr[p].Ml=inf;
		return ;
	}
	int mid=l+r>>1;
	pushdown(p);
	if(x<=mid) del(x,l,mid,p<<1);
	else del(x,mid+1,r,p<<1|1);
	return pushup(p);
}
void add(int x,int l,int r,int p) {
	if(l==r) {
		tr[p].Maxl=0,tr[p].tag=0;
		tr[p].Minl=pai(-1,0),tr[p].Mins=pai(flag[a[x].r]-flag[a[x].l]-(ask(a[x].r-1)-ask(a[x].l-1)),x);
		tr[p].Mr=a[x].r-1,tr[p].Ml=a[x].l;
		return ;
	}
	int mid=l+r>>1;pushdown(p);
	if(x<=mid) add(x,l,mid,p<<1);
	else add(x,mid+1,r,p<<1|1);
	return pushup(p);
}
void ins(int s,int t,int l,int r,int p,int &lim) {
	if(s>t) return ;
	if(s<=l&&r<=t) {
		int mid=l+r>>1;
		if(tr[p].Minl.x<lim) return ;
		if(l==r) {
			add(l,1,n,1);
			lim=max(lim,a[l].l);
			return ;
		}
		ins(s,t,l,mid,p<<1,lim);
		ins(s,t,mid+1,r,p<<1|1,lim);
		return pushup(p);
	}
	int mid=l+r>>1;pushdown(p);
	if(s<=mid) ins(s,t,l,mid,p<<1,lim);
	if(t>mid) ins(s,t,mid+1,r,p<<1|1,lim);
	return pushup(p);
}
int Ask(int x,int l,int r,int p) {
	if(l==r) return tr[p].Mins.x;
	int mid=l+r>>1;pushdown(p);
	if(x<=mid) return Ask(x,l,mid,p<<1);
	return Ask(x,mid+1,r,p<<1|1);
}
signed main() {
//	system("fc ex_ds1.out ds.out");
//	return 0;
//	freopen("ex_ds2.in","r",stdin);
//	freopen("ds.out","w",stdout);
//	freopen("ds.in","r",stdin);
//	freopen("ds.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) a[i].l=read()+1,a[i].r=read()+1,flag[++top]=a[i].l,flag[++top]=a[i].r,a[i].i=i;
	sort(flag+1,flag+top+1),top=unique(flag+1,flag+top+1)-flag-1;
	for(int i=1;i<=n;i++) a[i].l=lower_bound(flag+1,flag+top+1,a[i].l)-flag,a[i].r=lower_bound(flag+1,flag+top+1,a[i].r)-flag;
	sort(a+1,a+n+1);
	build(1,n,1,0);
//	puts("");
	for(int i=1;i<top;i++) st.insert(i),lst[i]=i-1,nxt[i]=i+1;
	nxt[0]=1,nxt[top-1]=0,lst[0]=top-1;
	for(int i=1;i<=n;i++) {
		int t=tr[1].Mins.y;
		if(tr[1].Mins.x) {
			for(int j=*st.lower_bound(a[t].l);j<a[t].r&&j;j=nxt[j]) 
				deal(j),lst[nxt[j]]=lst[j],nxt[lst[j]]=nxt[j];
			auto L=st.lower_bound(a[t].l),R=st.lower_bound(a[t].r);
			st.erase(L,R);
		}
		del(t,1,n,1);
		int ml=ask1(1,t-1,1,n,1),tlim=ask3(t+1,n,1,n,1);
		pai tmp;
		ins(t+1,tlim-1,1,n,1,ml);
//		printf("%d : ",a[t].i);
//		while((tmp=ask2(t+1,tlim-1,1,n,1)).x>=ml) 
//			add(tmp.y,1,n,1),ml=max(ml,a[tmp.y].l),printf("%d ",tmp.y);
//		puts("");
		wr(a[t].i,' ');
	}
	return 0;
}
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 10ms
memory: 73616kb

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

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: 4ms
memory: 75384kb

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: 3ms
memory: 74876kb

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: 3ms
memory: 74644kb

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: -100
Wrong Answer
time: 0ms
memory: 75640kb

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 65 75 67 70 84 94 95 77 79 88 96 98 80 89 91 83 85 86 92 93 97 99 100

result:

wrong answer 78th words differ - expected: '91', found: '65'
English 繁體中文 简体中文

伺服器時間: 2025-01-20 21:52:12 | 開源專案