QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#265853#7685. Barkley IIfishfishfriedfish#TL 170ms97708kbC++142.1kb2023-11-25 21:50:152023-11-25 21:50:16

Judging History

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

  • [2023-11-25 21:50:16]
  • 评测
  • 测评结果：TL
  • 用时：170ms
  • 内存：97708kb
查看
  • [2023-11-25 21:50:15]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define SZ(x) ((int)x.size()-1)
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b) for (int i=(a);i<=(b);++i)
#define DF(i,a,b) for (int i=(a);i>=(b);--i)
//#define mp make_pair
//#define OO(x) fixed<<setprecision(x)
using namespace std;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int read(){
	char ch=getchar(); int w=1,c=0;
	for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
	for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
	return w*c;
}
const int M=1e6+10;

struct fwt{
	int t[M],n;
	#define lowbit(x) (x&-x)
	void init(int _n){
		n=_n;
		F(i,0,n) t[i]=0;
	}
	void add(int x,int y){
		for (;x<=n;x+=lowbit(x)) t[x]+=y;
	}
	int qry(int x){
	    int ret=0;
	    for (;x;x^=lowbit(x)) ret+=t[x];
	    return ret;
	}
	
	inline int kth(int k){
	    int pos=0;
	    int cur=0;
	    DF(i,18,0){//attention!!!!
			pos^=(1<<i);
			if (pos>n || k<=t[pos]) pos^=(1<<i);
			else k-=t[pos];
		}
	    return pos+1;
	}
}A;



int n,m;
int a[M],cur[M];
struct node{
	int l,r,d;
};
vector<int> v[M];
vector<node> t[M];

void work(){
	n=read(); m=read();
	F(i,1,m) v[i].clear();
	F(i,1,n) t[i].clear();
	F(i,1,n){
		a[i]=read();
		v[a[i]].pb(i);
	}
	F(i,1,m) v[i].pb(n+1);
	F(i,1,m){
		int la=0; 
		for (int x:v[i]){
//			if (!x) continue;
			t[x-1].pb((node){la+1,x-1,i});
			la=x;			
		}
	}
	A.init(n);
	F(i,1,m) cur[i]=0;
	int ans=-1e9;
	F(i,1,n){
		if (cur[a[i]]) A.add(cur[a[i]],-1);
		cur[a[i]]=i;
		A.add(i,1);
		for (auto O:t[i]){
			if (O.l<=O.r){
//				cerr<<O.l<<" "<<O.r<<" "<<A.qry(i)-A.qry(O.l-1)<<" interval !!\n";
				ans=max(ans,A.qry(i)-A.qry(O.l-1)-O.d);
			}
		}
	}
	int o=0;
	F(i,1,m) if (cur[i]) o++;
	ans=max(ans,o-m-1);
	cout<<ans<<"\n";
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int T=read();
	while (T--) work(); return 0;
	return 0;
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 56556kb

input:

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

output:

2
3

result:

ok 2 number(s): "2 3"

Test #2:

score: 0
Accepted
time: 30ms
memory: 55528kb

input:

50000
10 19
12 6 1 12 11 15 4 1 13 18
10 8
8 7 6 7 6 2 2 3 4 8
10 6
3 2 6 6 5 2 3 4 5 6
10 11
6 3 7 9 2 1 2 10 10 4
10 6
6 1 2 6 1 1 3 4 2 1
10 9
8 5 3 9 1 7 5 5 1 1
10 5
1 4 3 2 5 4 5 3 5 2
10 14
3 8 12 10 4 2 3 13 7 3
10 14
5 5 12 2 8 1 13 9 8 5
10 7
5 5 6 6 1 5 3 7 3 4
10 7
5 1 4 6 1 6 4 3 7 5
10...

output:

6
5
4
4
2
4
3
7
4
4
4
5
2
3
6
6
7
5
7
6
5
5
6
2
6
8
7
2
5
5
6
2
2
3
4
5
3
3
7
3
2
5
6
1
3
5
3
3
3
8
6
6
5
7
4
4
5
4
6
6
6
3
7
3
6
3
3
7
7
6
6
7
4
3
3
4
4
6
3
4
6
6
4
5
5
9
4
5
7
5
3
5
2
2
5
6
6
8
4
3
4
5
5
5
7
7
3
2
6
5
3
5
4
4
5
6
6
5
6
7
7
4
5
7
4
7
3
7
6
6
6
5
4
2
5
4
2
3
6
5
2
6
5
5
4
3
5
6
6
6
...

result:

ok 50000 numbers

Test #3:

score: 0
Accepted
time: 36ms
memory: 56200kb

input:

100000
5 4
4 3 1 3 1
5 4
2 2 1 3 4
5 9
7 8 7 1 3
5 3
3 2 2 3 1
5 7
1 4 2 4 7
5 4
4 4 4 2 3
5 3
2 1 2 2 2
5 5
2 1 2 5 4
5 9
1 8 4 4 7
5 6
2 6 4 6 2
5 5
1 2 4 4 4
5 3
2 1 1 1 3
5 5
5 4 5 2 5
5 4
3 3 3 2 1
5 3
3 1 3 2 3
5 7
1 5 2 2 7
5 6
2 2 6 5 6
5 10
6 3 3 1 7
5 8
1 6 8 4 3
5 4
1 2 1 3 3
5 7
2 2 4 3 ...

output:

1
1
2
1
2
2
0
2
2
2
1
0
2
1
1
2
2
2
3
0
3
1
2
2
3
3
1
3
0
0
3
2
2
0
2
2
1
0
2
2
3
3
3
1
3
2
2
3
2
3
2
1
2
3
1
3
3
1
2
3
1
1
2
2
2
2
0
1
0
1
0
2
1
3
0
2
2
3
2
2
1
3
1
3
1
1
1
3
1
1
4
0
1
3
2
2
2
0
3
2
4
3
3
2
1
0
4
4
3
2
1
2
1
2
3
2
3
4
4
3
0
0
1
4
1
3
3
2
3
1
3
4
3
1
2
2
3
2
3
2
3
3
1
3
1
1
4
1
1
3
...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 23ms
memory: 54772kb

input:

25000
20 28
4 28 8 7 8 23 13 27 1 3 24 19 21 7 21 6 10 3 1 8
20 18
6 13 17 2 4 11 12 5 10 8 1 3 5 18 10 2 8 15 4 17
20 17
5 9 5 15 7 11 16 2 16 17 15 11 3 12 13 12 11 17 15 14
20 28
12 17 26 1 21 18 9 12 22 3 7 24 5 8 20 3 25 28 17 20
20 13
9 10 4 9 10 13 4 3 3 9 12 8 4 12 2 2 6 10 13 5
20 22
17 13 ...

output:

12
9
11
14
9
12
9
15
6
11
8
13
14
13
7
11
8
13
11
11
14
14
7
15
10
10
10
12
9
13
12
10
10
14
14
11
9
8
9
10
10
5
11
14
13
14
13
8
8
12
10
10
17
12
7
14
9
11
14
13
8
12
15
13
14
11
9
8
11
17
9
12
11
13
13
10
14
10
10
16
12
13
12
11
14
12
9
12
5
9
15
16
13
15
7
14
12
6
12
13
7
8
12
10
13
15
9
16
7
16
...

result:

ok 25000 numbers

Test #5:

score: 0
Accepted
time: 38ms
memory: 55068kb

input:

5000
100 100
71 48 44 27 73 73 90 42 69 81 79 99 97 3 45 78 38 92 89 27 97 7 4 91 42 59 7 45 88 100 15 66 64 6 26 54 38 38 72 81 15 94 35 63 33 85 100 16 41 5 71 20 92 36 39 59 19 59 11 22 11 26 94 29 73 98 16 16 47 25 35 50 49 6 67 85 69 90 6 87 72 24 37 62 55 54 25 38 95 14 15 26 89 26 25 46 14 24...

output:

59
78
69
48
78
53
64
73
53
66
59
57
62
42
73
69
46
68
66
47
59
64
71
57
73
43
52
66
67
61
66
66
65
58
80
65
65
69
75
76
69
39
69
61
53
72
44
62
63
71
76
56
69
79
49
73
62
71
83
59
70
53
69
73
47
68
74
59
66
74
75
61
53
76
48
62
79
71
47
72
40
80
62
42
63
70
72
70
70
59
68
56
74
54
61
78
68
75
70
39
...

result:

ok 5000 numbers

Test #6:

score: 0
Accepted
time: 112ms
memory: 87092kb

input:

2
250000 144237
103523 38477 80037 110169 8464 110583 60349 74339 29012 8989 96955 23403 38383 12186 107503 109176 1709 31839 109579 62912 130470 26082 102718 25272 17893 55607 48053 34513 23154 136492 8313 136454 57920 60639 68601 50656 16871 101625 88777 35367 62644 80269 24346 33961 74832 62520 8...

output:

118705
195099

result:

ok 2 number(s): "118705 195099"

Test #7:

score: 0
Accepted
time: 170ms
memory: 97708kb

input:

1
500000 500000
166333 42890 491246 340568 331305 268296 201428 53022 200493 362616 82079 492836 402998 214609 161141 471977 378791 107806 182516 265636 468917 104158 490409 221339 116329 325539 49370 262861 37122 78932 236317 431273 76912 177034 393086 455348 481306 290838 435357 444359 465017 1894...

output:

315937

result:

ok 1 number(s): "315937"

Test #8:

score: -100
Time Limit Exceeded

input:

50000
10 359848
3 7 9 4 5 2 8 10 1 6
10 418109
5 3 9 4 8 10 6 2 1 7
10 218272
3 4 6 5 2 1 9 10 8 7
10 35311
10 8 7 3 9 2 1 6 5 4
10 82600
4 10 6 9 7 5 2 1 3 8
10 265069
10 5 3 2 9 4 1 8 7 6
10 105624
7 2 3 1 9 10 5 8 4 6
10 440218
10 5 3 6 9 4 1 8 7 2
10 444968
1 2 4 7 5 10 3 9 8 6
10 199453
7 10 1 ...

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-05 10:09:25 | 开源项目