#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
struct Node {
Node *left;
Node *right;
int mn,mx,lazy,children;
Node() : left(NULL), right(NULL), mn(0), mx(0), lazy(0), children(0) {};
void update(){
mx=max(left->mx, right->mx);
mn=min(left->mn, right->mn);
children=left->children+right->children;
}
};
Node *NODE;
int D;
void propagate(Node* root){
if(root->lazy>0){
if(root->left) root->left->lazy+=root->lazy;
if(root->right) root->right->lazy+=root->lazy;
root->mn+=D*root->lazy;
root->mx+=D*root->lazy;
root->lazy=0;
}
}
void build(Node* root, int l, int r){
if(l==r) {
root->mx=-1e18;
root->mn=1e18;
return;
}
int mid=(l+r)/2;
root->left=new Node;
root->right=new Node;
build(root->left,l,mid);
build(root->right,mid+1,r);
root->update();
}
pair<int,int> minmax(Node* root, int l, int r, int ql, int qr){
propagate(root);
if(qr<l||ql>r) return {1e18, -1e18};
if(ql<=l&&r<=qr){
return {root->mn, root->mx};
}
int mid=(l+r)/2;
pair<int,int> a,b;
a=minmax(root->left,l,mid,ql,qr);
b=minmax(root->right,mid+1,r,ql,qr);
return {min(a.first,b.first), max(a.second,b.second)};
}
int kthPos(Node* root, int l, int r, int ql, int qr){
if(qr<l||ql>r) return 0;
if(ql<=l&&r<=qr){
return root->children;
}
int mid=(l+r)/2;
pair<int,int> a,b;
return kthPos(root->left,l,mid,ql,qr)+kthPos(root->right,mid+1,r,ql,qr);
}
void update(Node* root, int l, int r, int p, int v){
propagate(root);
if(r<p||l>p) return;
if(l==p&&r==p){
root->mn=v;
root->mx=v;
root->children=1;
return;
}
int mid=(l+r)/2;
update(root->left,l,mid,p,v);
update(root->right,mid+1,r,p,v);
root->update();
}
void updateLAZY(Node* root, int l, int r, int ql, int qr){
if(r<ql||l>qr) return;
if(l>=ql&&r<=qr){
root->lazy++;
propagate(root);
return;
}
propagate(root);
int mid=(l+r)/2;
updateLAZY(root->left,l,mid,ql,qr);
updateLAZY(root->right,mid+1,r,ql,qr);
root->update();
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n,m; cin >> n >> m >> D;
if(n==0){
NODE=new Node;
vector<pair<int,int>> asort(m);
vector<pair<int,int>> a(m);
for (int i = 0; i < m; i++)
{
cin >> a[i].first;
asort[i]={a[i].first,i};
}
sort(asort.begin(),asort.end());
for (int i = 0; i < m; i++) a[asort[i].second].second=i;
build(NODE, 0, m-1);
int retMax=0;
for (int _i = 0; _i < m; _i++)
{
int x=a[_i].first;
update(NODE, 0, m-1, a[_i].second, (kthPos(NODE, 0, m-1, 0, a[_i].second)*D)-x);
updateLAZY(NODE, 0, m-1, a[_i].second+1, m-1);
int cmin=minmax(NODE, 0, m-1, 0, a[_i].second).first;
int cmax=minmax(NODE, 0, m-1, a[_i].second, m-1).second;
retMax=max(cmax-cmin, retMax);
if(retMax%2==0) cout << retMax/2LL << " ";
else cout << retMax/2LL << ".5 ";
}
cout << "\n";
}else{
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int _i = 0; _i < m; _i++)
{
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int _i = 0; _i < m; _i++)
{
int x; cin >> x;
a.push_back(x);
sort(a.begin(),a.end());
double l=0,r=2000000000000000;
double ans=0;
while(r-l>=0.1){
double mid=(l+r)/(double)2;
double lb=a[0]-mid;
bool br=false;
for (int i = 1; i < a.size(); i++)
{
double bc=max(lb+(double)D, (double)a[i]-mid);
if(bc>(double)a[i]+mid) {
br=true;
break;
}
lb=bc;
}
if(br){
l=mid;
}else{
ans=mid;
r=mid;
}
}
int roundAns=ans;
if((double)ans-roundAns<0.25) cout << roundAns << " ";
else if ((double)ans-roundAns<0.75) cout << roundAns << ".5 ";
else cout << roundAns+1 << " ";
}
cout << "\n";
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:142:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (int i = 1; i < a.size(); i++)
| ~~^~~~~~~~~~
Main.cpp:168:1: error: expected '}' at end of input
168 | }
| ^
Main.cpp:96:15: note: to match this '{'
96 | signed main() {
| ^
