QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#821562 | #9064. A Cappella Recording | LaVuna47# | AC ✓ | 20ms | 8648kb | C++17 | 1.8kb | 2024-12-19 16:38:04 | 2024-12-19 16:38:04 |
Judging History
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'