QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#821562#9064. A Cappella RecordingLaVuna47#AC ✓20ms8648kbC++171.8kb2024-12-19 16:38:042024-12-19 16:38:04

Judging History

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

  • [2024-12-19 16:38:04]
  • 评测
  • 测评结果:AC
  • 用时:20ms
  • 内存:8648kb
  • [2024-12-19 16:38:04]
  • 提交

answer

/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, st_, n) for(int i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(int i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

/*
3 1 4 1 5 9

1 1 3 4 5 9
*/

int solve()
{
	ll n, d;
	if(!(cin>>n>>d))
		return 1;
	vector<ll> a(n);
	FOR(i,0,n)cin>>a[i];
	sort(all(a));
	set<ll> S;
	int res=0;
	FOR(i,0,n)
	{
		if(S.empty())
		{
			S.insert(a[i]);
			++res;
		}
		else
		{
			if(abs(a[i]- (*S.begin()))>d ||abs(a[i]- (*S.rbegin())) > d)
			{
				S.clear();
				++res;
				S.insert(a[i]);
			}
			else
			{
				S.insert(a[i]);
			}
		}
	}
	cout<<res<<'\n';
    return 0;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1e9;
    //cin >> TET;
    for (int i = 1; i <= TET; i++)
    {
        if (solve())
        {
            break;
        }
#ifdef ONPC
        cout << "__________________________" << endl;
#endif
    }
#ifdef ONPC
    cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

详细

Test #1:

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

input:

6 0
3
1
4
1
5
9

output:

5

result:

ok single line: '5'

Test #2:

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

input:

6 1
3
1
4
1
5
9

output:

4

result:

ok single line: '4'

Test #3:

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

input:

6 2
3
1
4
1
5
9

output:

3

result:

ok single line: '3'

Test #4:

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

input:

6 4
3
1
4
1
5
9

output:

2

result:

ok single line: '2'

Test #5:

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

input:

6 8
3
1
4
1
5
9

output:

1

result:

ok single line: '1'

Test #6:

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

input:

1 0
0

output:

1

result:

ok single line: '1'

Test #7:

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

input:

1 1000000000
0

output:

1

result:

ok single line: '1'

Test #8:

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

input:

1 0
1000000000

output:

1

result:

ok single line: '1'

Test #9:

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

input:

1 1000000000
1000000000

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 5ms
memory: 3928kb

input:

100000 0
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
...

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 5ms
memory: 3872kb

input:

100000 1000000000
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
39
...

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 7ms
memory: 4060kb

input:

100000 0
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
1...

output:

100000

result:

ok single line: '100000'

Test #13:

score: 0
Accepted
time: 20ms
memory: 8648kb

input:

100000 1000000000
0
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
110000
120000
130000
140000
150000
160000
170000
180000
190000
200000
210000
220000
230000
240000
250000
260000
270000
280000
290000
300000
310000
320000
330000
340000
350000
360000
370000
380000
390000
400000
410000
42...

output:

1

result:

ok single line: '1'

Test #14:

score: 0
Accepted
time: 15ms
memory: 3940kb

input:

100000 100000
163790331
424101753
271375616
594626695
714814667
324476341
27568655
104086474
514864280
770793200
693707633
40007660
917322413
526600662
188521244
701903336
646686162
924577105
173641141
263963532
583493590
861489992
669629021
356682256
601328331
644282255
115618964
260033555
54096802...

output:

9099

result:

ok single line: '9099'

Test #15:

score: 0
Accepted
time: 12ms
memory: 3968kb

input:

100000 1000000
910494600
849063336
8378792
533375801
27955236
267019376
507909
603013889
420223655
947222394
476724577
639758766
809221428
58892341
903465332
30699945
539574952
906152551
766229254
21241239
669028791
320931479
215479062
534206455
313858521
30029226
964386507
184386086
498686425
66694...

output:

990

result:

ok single line: '990'

Test #16:

score: 0
Accepted
time: 17ms
memory: 3940kb

input:

100000 10000000
870074907
308894179
996412889
233938114
326227678
131057112
582552854
397256247
783962359
546325719
405575641
242620544
960492619
559407438
981146036
500363019
361908630
999505540
170056234
6310847
374948547
527794341
129885683
299581112
35310012
936869712
693157444
332024592
1777570...

output:

100

result:

ok single line: '100'

Test #17:

score: 0
Accepted
time: 19ms
memory: 4496kb

input:

100000 100000000
821227742
746003463
441035399
683684865
121183194
34386928
346392152
335197544
601858430
992444390
520463840
170754383
332054259
329655686
820176279
142091613
79541627
933706054
899983451
348395780
250443764
954078163
377795338
409257306
346167101
830912105
101166984
183938717
75181...

output:

10

result:

ok single line: '10'