QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#456212#964. Excluded Min541foreverTL 2ms10112kbC++203.8kb2024-06-27 14:10:482024-06-27 14:10:49

Judging History

This is the latest submission verdict.

  • [2024-06-27 14:10:49]
  • Judged
  • Verdict: TL
  • Time: 2ms
  • Memory: 10112kb
  • [2024-06-27 14:10:48]
  • Submitted

answer

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
	int s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
struct node
{
	int l,r,id;
}q[500001];
int qans[500001];
int num[2000001];
int tag[2000001];
int a[500001];
int n,m,sq;
inline void T(int p,int y)
{
	tag[p]+=y,num[p]+=y;
}
inline void push_down(int p)
{
	T(p*2,tag[p]);
	T(p*2|1,tag[p]);
	tag[p]=0;
}
inline void push_up(int p)
{
	num[p]=max(num[p*2],num[p*2|1]);
}
void build(int p,int pl,int pr)
{
	if(pl==pr)
	{
		num[p]=-pl;
		return ;
	}
	int mid=(pl+pr)>>1;
	build(p*2,pl,mid);
	build(p*2|1,mid+1,pr);
	push_up(p);
}
void add(int p,int pl,int pr,int l,int r,int y)
{
	if(l<=pl&&pr<=r){ T(p,y);return ;}
	int mid=(pl+pr)>>1;push_down(p);
	if(l<=mid) add(p*2,pl,mid,l,r,y);
	if(mid<r) add(p*2|1,mid+1,pr,l,r,y);
	push_up(p);
}
int get(int p,int pl,int pr)
{
	if(pl==pr) return pl;
	int mid=(pl+pr)>>1;push_down(p);
	if(num[p*2|1]>=0) return get(p*2|1,mid+1,pr);
	return get(p*2,pl,mid);
}
inline void add(int x,int y)
{
	if(x>n) return ;
	add(1,0,n,x,n,y);
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read()+1;
	for(;(sq+1)*(sq+1)<=n;sq++);
	for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;
	build(1,0,n);

	sort(q+1,q+m+1,[](node a,node b)
	{
		if(a.l/sq!=b.l/sq) return a.l<b.l;
		return a.r<b.r;
	});

	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(r<q[i].r) add(a[++r],1);
		while(l>q[i].l) add(a[--l],1); 
		while(r>q[i].r) add(a[r--],-1);
		while(l<q[i].l) add(a[l++],-1);
		qans[q[i].id]=get(1,0,n);
	}
	for(int i=1;i<=m;i++) printf("%d\n",qans[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3
0 0 2
1 3
2 3
3 3

output:

3
1
0

result:

ok 3 number(s): "3 1 0"

Test #2:

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

input:

3 2
1 2 2
1 2
1 3

output:

0
3

result:

ok 2 number(s): "0 3"

Test #3:

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

input:

10 10
3 0 3 3 9 7 9 6 0 7
3 3
9 9
4 6
1 9
3 4
2 4
7 10
3 7
5 7
2 7

output:

0
1
0
5
0
1
1
0
0
1

result:

ok 10 numbers

Test #4:

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

input:

10 10
3 0 0 0 5 1 1 1 2 1
1 2
8 8
5 7
1 7
2 2
1 5
5 6
4 6
3 10
6 8

output:

1
0
2
7
1
4
0
2
8
3

result:

ok 10 numbers

Test #5:

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

input:

100 100
15 82 7 39 63 55 64 99 71 63 32 99 67 94 3 43 15 75 45 55 53 4 35 36 15 40 82 20 62 43 6 83 27 95 27 45 98 44 35 98 39 7 17 32 76 7 40 16 40 63 13 8 22 27 11 12 61 14 19 45 100 97 90 88 22 59 25 63 4 25 65 16 22 92 84 44 99 66 89 26 93 97 35 97 92 1 32 40 97 97 78 43 7 12 23 53 61 74 33 90
1...

output:

68
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
48
0
0
0
0
0
0
0
0
0
0
0
0
0
28
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 100 numbers

Test #6:

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

input:

100 100
17 86 33 8 11 27 8 11 13 9 3 43 11 23 26 42 44 12 44 12 15 0 75 51 72 5 49 2 40 57 24 47 39 42 4 5 6 52 3 2 42 19 62 33 24 22 16 69 4 33 44 70 29 11 2 2 58 9 6 10 25 10 33 26 17 3 14 0 48 7 48 51 0 39 54 37 14 9 3 85 18 4 25 9 2 0 39 8 17 13 25 45 10 39 12 18 9 5 66 6
13 89
10 90
42 67
43 52...

output:

76
80
0
0
18
1
18
1
5
5
1
1
22
11
0
15
0
59
5
56
1
80
0
1
1
21
0
61
22
11
0
3
8
15
40
1
8
81
71
20
2
0
60
0
60
31
0
59
0
0
0
28
0
21
1
7
5
0
31
0
76
28
0
0
27
1
23
0
1
27
1
0
0
1
0
5
63
52
2
43
73
1
86
0
61
0
27
2
30
5
31
1
0
14
59
27
1
1
67
63

result:

ok 100 numbers

Test #7:

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

input:

100 100
6 1 1 5 13 11 35 5 3 2 0 4 0 9 1 2 3 3 19 1 7 9 7 11 7 8 10 18 28 17 31 2 4 8 2 3 3 2 22 4 9 4 7 2 9 15 8 2 3 19 5 24 3 10 11 5 9 20 8 4 11 10 18 9 13 34 5 34 2 9 24 6 21 16 6 12 26 2 2 2 6 11 2 14 3 8 2 12 2 19 8 3 18 23 5 21 23 8 4 0
44 67
25 74
24 79
59 73
4 81
42 66
48 55
15 38
35 63
16 ...

output:

22
50
56
0
78
23
0
22
29
24
38
37
17
57
0
6
0
58
52
4
64
44
0
37
75
75
34
89
0
4
0
12
39
0
0
69
53
14
38
13
36
30
0
7
46
83
28
6
44
22
40
50
24
26
36
49
0
0
6
49
27
78
0
37
11
49
16
50
25
30
37
58
64
28
62
36
0
52
0
95
34
4
50
17
0
27
44
0
0
21
44
66
69
0
39
25
0
2
63
0

result:

ok 100 numbers

Test #8:

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

input:

100 100
0 1 0 1 0 1 1 1 0 2 1 1 2 0 1 1 0 3 0 0 0 0 0 0 0 0 1 2 2 0 0 0 0 1 0 0 1 2 0 0 1 0 0 3 0 1 0 0 3 0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 2 0 0 0 4 0 1 1 0 1 0 2 2 0 0 1
41 53
31 36
78 99
60 86
1 67
3 92
89 92
60 70
42 56
42 46
39 84
40 66
9 27
75 78
33 94
17 53...

output:

13
6
22
27
67
90
3
11
15
5
46
27
19
4
62
37
84
35
53
4
47
95
55
63
24
39
22
51
67
21
55
36
24
16
33
74
4
16
63
81
41
14
3
54
6
40
36
33
29
32
14
60
13
17
73
44
34
2
14
79
59
13
75
72
31
10
22
57
23
37
74
2
6
6
38
5
4
62
66
22
33
0
23
21
12
54
75
6
8
16
37
36
3
53
63
18
67
60
31
19

result:

ok 100 numbers

Test #9:

score: -100
Time Limit Exceeded

input:

300000 300000
216504 101790 177261 84423 215788 67188 170620 125383 222808 149722 190483 152974 27524 172557 109218 201761 138030 177265 270417 244027 29296 13565 108388 270622 75102 137755 134081 21988 249714 268911 178911 39288 197287 232628 152784 226739 40134 213404 230781 181323 235763 55745 44...

output:


result: