#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;
struct link{
ll x,l,r;
link(ll x):x(x),l(0),r(0) {}
};
struct Node{
ll ans,pl,pr,sum;
ll l,r;
Node *lft,*rt;
void pu() {
sum=lft->sum+rt->sum;
pl=max(lft->pl,lft->sum+rt->pl);
pr=max(rt->pr,rt->sum+lft->pr);
ans=max({lft->ans,rt->ans,lft->pr+rt->pl});
}
Node(int l,int r,vector<ll> &dif):l(l),r(r),lft(nullptr),rt(nullptr) {
if (l==r) {
sum=dif[l];
pl=max(0ll,dif[l]);
pr=max(0ll,dif[l]);
ans=max(0ll,dif[l]);
return;
}
int mid=l+r>>1;
lft = new Node(l,mid,dif);
rt = new Node(mid+1,r,dif);
pu();
// cout<<l<<" "<<r<<" "<<sum<<" "<<pl<<" "<<pr<<" "<<ans<<" l r sum pl pr ans\n";
}
void update(int tar,ll val) {
if (l==r) {
sum=val;
pl=max(0ll,val);
pr=max(0ll,val);
ans=max(0ll,val);
return;
}
int mid=l+r>>1;
if (tar<=mid) lft->update(tar,val);
else rt->update(tar,val);
pu();
}
};
int main() {
speed;
ll n,m,d;
cin>>n>>m>>d;
vector<link> pos;
vector<ll> pm(m);
for (int i=0;i<n;i++) {
ll x;
cin>>x;
pos.push_back(link(x));
}
for (int i=0;i<m;i++) {
cin>>pm[i];
pos.push_back(link(pm[i]));
}
map<ll,vector<int>> vtp;
sort(all(pos),[&](link a,link b) {
return a.x<b.x;
});
int tn=pos.size();
for (int i=0;i<tn;i++) {
vtp[pos[i].x].push_back(i);
pos[i].l=i-1;
pos[i].r=i+1;
}
vector<ll> dif(tn);
for (int i=1;i<tn;i++) {
dif[i]=d-(pos[i].x-pos[i-1].x);
}
Node *rt = new Node(1,tn-1,dif);
vector<ll> ans(m);
for (int i=m-1;i>=0;i--) {
ans[i]=rt->ans;
ll dp = vtp[pm[i]].back();
vtp[pm[i]].pop_back();
rt->update(dp,0);
ll pr=pos[i].r,pl=pos[i].l;
if (pr!=tn and pl!=-1) {
rt->update(pr,d-(pos[pr].x-pos[pl].x));
}
if (pr!=tn) pos[pr].l=pl;
if (pl!=-1) pos[pl].r=pr;
}
for (int i=0;i<m;i++) cout<<.5*ans[i]<<" ";
return 0;
}
Compilation message
Main.cpp: In constructor 'Node::Node(int, int, std::vector<long long int>&)':
Main.cpp:49:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int mid=l+r>>1;
| ~^~
Main.cpp: In member function 'void Node::update(int, ll)':
Main.cpp:63:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
848 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
848 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
234 ms |
67384 KB |
Output is correct |
| 2 |
Incorrect |
276 ms |
68648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
234 ms |
67384 KB |
Output is correct |
| 2 |
Incorrect |
276 ms |
68648 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
