QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#880753#8612. The Best WifeNKheyuxiangWA 0ms8016kbC++14539b2025-02-03 19:34:212025-02-03 19:34:21

Judging History

This is the latest submission verdict.

  • [2025-02-03 19:34:21]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 8016kb
  • [2025-02-03 19:34:21]
  • Submitted

answer

#include<bits/stdc++.h>
#define N 600005
using namespace std;
const int B=750;
int n,l,r,x,y,w,m;
int go[N],to[N],ct[N];
void tr(){
	if(go[x]>r){
		go[x]=r;
		if(r/B==x/B) to[x]=to[r],ct[x]=ct[r]+1;
	}
}
int main(){
	scanf("%d",&n);
	m=2*n+2;
	for(int i=0;i<m;i++) go[i]=m,to[i]=i;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&l,&r);r++;
		for(x=l;x%B!=0;x--) tr();
		tr();
		w=x=0;y=m;
		while(x<=2*n){
			y=min(y,go[x]);
			if(y<x+B){
				w+=1+ct[y];
				y=go[to[y]];
			}
			x+=B;
		}
		printf("%d\n",w);
	} 
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8012kb

input:

5
1 3
3 5
1 2
5 6
4 4

output:

1
1
2
2
3

result:

ok 5 number(s): "1 1 2 2 3"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 8016kb

input:

100
67 72
1 100
61 65
87 91
19 77
47 97
3 85
64 97
6 92
33 36
7 27
33 44
13 98
3 62
36 97
26 39
7 35
2 92
8 64
37 83
5 89
26 87
6 96
58 71
49 96
3 85
27 65
16 93
26 70
8 97
1 100
8 93
5 59
9 92
9 99
1 100
8 81
7 66
4 78
12 52
28 42
1 36
2 100
75 81
26 61
8 86
4 44
58 74
29 100
40 77
83 100
39 59
3 9...

output:

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

result:

wrong answer 4th numbers differ - expected: '3', found: '2'