#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
const ll inf = 2e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
mt19937 _rand(time(NULL));
const int mxn = 5e5;
ll n, d, T;
ll a[mxn];
ll pr[mxn];
pii seg[2*mxn];
ll t[2*mxn];
int l(int k){
return 2*k;
}
int r(int k){
return 2*k+1;
}
void push(int k){
t[l(k)] += t[k];
t[r(k)] += t[k];
t[k] = 0;
}
void upd(int k){
pii lef = {seg[l(k)].st + t[l(k)], seg[l(k)].nd};
pii rig = {seg[r(k)].st + t[r(k)], seg[r(k)].nd};
seg[k] = min(lef, rig);
}
void build(int k, int l, int r){
seg[k] = {inf, 0};
t[k] = 0;
if(l == r){
return;
}
int mid = (l+r)/2;
build(::l(k), l, mid);
build(::r(k), mid+1, r);
}
void Insert(int k, int l, int r, int pos, ll val, ll C){
if(r < pos || pos < l) return;
if(l == r){
seg[k].st = val;
seg[k].nd = C;
t[k] = 0;
return;
}
push(k);
int mid = (l+r)/2;
Insert(::l(k), l, mid, pos, val, C);
Insert(::r(k), mid+1, r, pos, val, C);
upd(k);
}
void update(int k, int l, int r, int x, int y, ll val){
if(r < x || y < l) return;
if(x <= l && r <= y){
t[k] += val;
return;
}
push(k);
int mid = (l+r)/2;
update(::l(k), l, mid, x, y, val);
update(::r(k), mid+1, r, x, y, val);
upd(k);
}
pii dp[mxn];
int TOT = 0;
int sure = 0;
void g(ll lambda){
build(1, 0, n);
Insert(1, 0, n, 0, 0, 0);
fr(i, 0, n){
if(pr[i] != -1 && pr[i] != i){
update(1, 0, n, 0, pr[i], 1);
}
pii bst = {seg[1].st + t[1], seg[1].nd};
dp[i] = {bst.st + lambda, bst.nd+1};
Insert(1, 0, n, i+1, dp[i].st, dp[i].nd);
}
dp[n-1].nd--;
dp[n-1].st -= lambda;
}
ll aliens(){
ll l = 0, r = n+1;
ll best_lambda = 0;
while(l <= r){
ll mid = (l+r)/2;
g(mid);
if(dp[n-1].nd >= d){
best_lambda = mid;
l = mid+1;
}
else{
r = mid-1;
}
}
g(best_lambda);
if(dp[n-1].nd > d){
ll a1 = dp[n-1].st - best_lambda*dp[n-1].nd;
ll c1 = dp[n-1].nd;
g(best_lambda+1);
ll a2 = dp[n-1].st - (best_lambda+1)*dp[n-1].nd;
ll c2 = dp[n-1].nd;
return a2 + (a1-a2)*(d-c2)/(c1-c2);
}
return dp[n-1].st - best_lambda*dp[n-1].nd;
}
void solve(){
cin >> n >> d >> T;
fr(i, 0, n){
cin >> a[i];
}
stack<int> S;
fr(i, 0, n){
if(a[i] <= T){
pr[i] = i;
while(!S.empty() && a[S.top()] + i - S.top() >= a[i]){
S.pop();
}
S.push(i);
}
else{
while(!S.empty() && a[S.top()] + i - S.top() > T){
S.pop();
}
if(S.empty()){
pr[i] = -1;
}
else{
pr[i] = S.top();
}
}
}
fr(i, 0, n){
if(pr[i] == -1) continue;
if(pr[i] == i) sure ++;
TOT ++;
}
cout<<sure+aliens()<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
4 ms |
460 KB |
Output is correct |
8 |
Correct |
4 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Execution timed out |
2072 ms |
42044 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
4 ms |
460 KB |
Output is correct |
8 |
Correct |
4 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
3 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
332 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
2 ms |
332 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
332 KB |
Output is correct |
23 |
Correct |
22 ms |
676 KB |
Output is correct |
24 |
Correct |
21 ms |
588 KB |
Output is correct |
25 |
Correct |
21 ms |
680 KB |
Output is correct |
26 |
Correct |
21 ms |
676 KB |
Output is correct |
27 |
Correct |
21 ms |
676 KB |
Output is correct |
28 |
Correct |
21 ms |
672 KB |
Output is correct |
29 |
Correct |
22 ms |
588 KB |
Output is correct |
30 |
Correct |
20 ms |
588 KB |
Output is correct |
31 |
Correct |
24 ms |
672 KB |
Output is correct |
32 |
Correct |
20 ms |
588 KB |
Output is correct |
33 |
Correct |
19 ms |
676 KB |
Output is correct |
34 |
Correct |
25 ms |
628 KB |
Output is correct |
35 |
Correct |
21 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
771 ms |
8840 KB |
Output is correct |
3 |
Correct |
659 ms |
8900 KB |
Output is correct |
4 |
Correct |
727 ms |
8884 KB |
Output is correct |
5 |
Correct |
694 ms |
8848 KB |
Output is correct |
6 |
Correct |
695 ms |
8844 KB |
Output is correct |
7 |
Correct |
648 ms |
8844 KB |
Output is correct |
8 |
Correct |
635 ms |
8844 KB |
Output is correct |
9 |
Correct |
793 ms |
8840 KB |
Output is correct |
10 |
Correct |
621 ms |
8844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
4 ms |
460 KB |
Output is correct |
8 |
Correct |
4 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
2 ms |
332 KB |
Output is correct |
14 |
Correct |
3 ms |
332 KB |
Output is correct |
15 |
Correct |
2 ms |
332 KB |
Output is correct |
16 |
Correct |
2 ms |
332 KB |
Output is correct |
17 |
Correct |
2 ms |
332 KB |
Output is correct |
18 |
Correct |
2 ms |
332 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
2 ms |
332 KB |
Output is correct |
23 |
Correct |
22 ms |
676 KB |
Output is correct |
24 |
Correct |
21 ms |
588 KB |
Output is correct |
25 |
Correct |
21 ms |
680 KB |
Output is correct |
26 |
Correct |
21 ms |
676 KB |
Output is correct |
27 |
Correct |
21 ms |
676 KB |
Output is correct |
28 |
Correct |
21 ms |
672 KB |
Output is correct |
29 |
Correct |
22 ms |
588 KB |
Output is correct |
30 |
Correct |
20 ms |
588 KB |
Output is correct |
31 |
Correct |
24 ms |
672 KB |
Output is correct |
32 |
Correct |
20 ms |
588 KB |
Output is correct |
33 |
Correct |
19 ms |
676 KB |
Output is correct |
34 |
Correct |
25 ms |
628 KB |
Output is correct |
35 |
Correct |
21 ms |
588 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
771 ms |
8840 KB |
Output is correct |
38 |
Correct |
659 ms |
8900 KB |
Output is correct |
39 |
Correct |
727 ms |
8884 KB |
Output is correct |
40 |
Correct |
694 ms |
8848 KB |
Output is correct |
41 |
Correct |
695 ms |
8844 KB |
Output is correct |
42 |
Correct |
648 ms |
8844 KB |
Output is correct |
43 |
Correct |
635 ms |
8844 KB |
Output is correct |
44 |
Correct |
793 ms |
8840 KB |
Output is correct |
45 |
Correct |
621 ms |
8844 KB |
Output is correct |
46 |
Correct |
1 ms |
332 KB |
Output is correct |
47 |
Correct |
2 ms |
332 KB |
Output is correct |
48 |
Correct |
2 ms |
332 KB |
Output is correct |
49 |
Correct |
3 ms |
332 KB |
Output is correct |
50 |
Correct |
2 ms |
332 KB |
Output is correct |
51 |
Correct |
2 ms |
332 KB |
Output is correct |
52 |
Correct |
2 ms |
392 KB |
Output is correct |
53 |
Correct |
2 ms |
332 KB |
Output is correct |
54 |
Correct |
3 ms |
392 KB |
Output is correct |
55 |
Correct |
2 ms |
332 KB |
Output is correct |
56 |
Correct |
2 ms |
332 KB |
Output is correct |
57 |
Correct |
24 ms |
588 KB |
Output is correct |
58 |
Correct |
20 ms |
640 KB |
Output is correct |
59 |
Correct |
21 ms |
588 KB |
Output is correct |
60 |
Correct |
21 ms |
684 KB |
Output is correct |
61 |
Correct |
21 ms |
600 KB |
Output is correct |
62 |
Correct |
25 ms |
588 KB |
Output is correct |
63 |
Correct |
27 ms |
588 KB |
Output is correct |
64 |
Correct |
24 ms |
680 KB |
Output is correct |
65 |
Correct |
20 ms |
676 KB |
Output is correct |
66 |
Correct |
22 ms |
672 KB |
Output is correct |
67 |
Correct |
19 ms |
672 KB |
Output is correct |
68 |
Correct |
21 ms |
680 KB |
Output is correct |
69 |
Correct |
25 ms |
588 KB |
Output is correct |
70 |
Correct |
1 ms |
332 KB |
Output is correct |
71 |
Correct |
752 ms |
8844 KB |
Output is correct |
72 |
Correct |
668 ms |
8844 KB |
Output is correct |
73 |
Correct |
757 ms |
8900 KB |
Output is correct |
74 |
Correct |
687 ms |
8848 KB |
Output is correct |
75 |
Correct |
709 ms |
8848 KB |
Output is correct |
76 |
Correct |
634 ms |
8840 KB |
Output is correct |
77 |
Correct |
628 ms |
8840 KB |
Output is correct |
78 |
Correct |
825 ms |
8840 KB |
Output is correct |
79 |
Correct |
664 ms |
8840 KB |
Output is correct |
80 |
Correct |
669 ms |
8848 KB |
Output is correct |
81 |
Correct |
715 ms |
8848 KB |
Output is correct |
82 |
Correct |
655 ms |
8844 KB |
Output is correct |
83 |
Correct |
748 ms |
8860 KB |
Output is correct |
84 |
Correct |
746 ms |
8848 KB |
Output is correct |
85 |
Correct |
745 ms |
8844 KB |
Output is correct |
86 |
Correct |
696 ms |
8900 KB |
Output is correct |
87 |
Correct |
655 ms |
8848 KB |
Output is correct |
88 |
Correct |
714 ms |
8848 KB |
Output is correct |
89 |
Correct |
818 ms |
8848 KB |
Output is correct |
90 |
Correct |
755 ms |
8844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
2 ms |
332 KB |
Output is correct |
3 |
Correct |
2 ms |
332 KB |
Output is correct |
4 |
Correct |
2 ms |
332 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
332 KB |
Output is correct |
7 |
Correct |
4 ms |
460 KB |
Output is correct |
8 |
Correct |
4 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
332 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Execution timed out |
2072 ms |
42044 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |