#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mod 998244353
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<pair<pair<int,int>,int>,null_type,less<pair<pair<int,int>,int>>,rb_tree_tag,tree_order_statistics_node_update>;
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,m,d;
cin>>n>>m>>d;
if(!n){
d*=2;
deque<pair<int,int>>a,b;
int tt=0,l=0,r=0,ans=0;
while(m--){
int x;
cin>>x;
x*=2;
ans+=(a.size()?max(0ll,d-(x-a.back().first)):0);
a.push_back({x,(a.size()?max(0ll,d-(x-a.back().first))+a.back().second:0)});
if(b.size())tt+=max(0ll,d-(x-b.back().first));
b.push_back({x,-tt});
// cout<<ans<<' ';
while(r+1<a.size()||l<r){
if(l<r){
int k=max(a.back().second-a[r].second,(b[0].second)-(b[r].second));
// cout<<r<<' '<<b[0].second-b[r].second<<' ';
if(k<=ans){
ans=k;
l++;
}else break;
}else{
int A=a.back().second-a[r+1].second,B=b[0].second-b[r].second;
int K=max(A,B)+max(0ll,(d-(a[r+1].first-a[r].first))-(max(A,B)-min(A,B))/2)/2;
int k=max(A,B)+max(0ll,(d-(a[r+1].first-a[r].first)))/2;
// cout<<'f'<<K<<' '<<k<<'f';
if(K<=ans){
ans=K;
// cout<<'g'<<ans<<'g';
r++;
}else break;
}
}
cout<<ans/2;
if(ans&1)cout<<".5";
cout<<' ';
}
}else{
}
}
/*
1
13
7 10 13 |4 |5 10| 8| 3 6 5 |7 10| 2
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:27:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | while(r+1<a.size()||l<r){
| ~~~^~~~~~~~~
Main.cpp:38:25: warning: unused variable 'k' [-Wunused-variable]
38 | int k=max(A,B)+max(0ll,(d-(a[r+1].first-a[r].first)))/2;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
10364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
10364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
