#include <bits/stdc++.h>
#define int long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.begin(), x.end()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
using namespace std;
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const int N = 2e5 + 5;
const int INF = 1e17;
struct Node {
int mn, mx, sum, tag;
int lc, rc;
Node() : mn(INF), mx(-INF), sum(0), tag(0), lc(-1), rc(-1) {}
};
int D;
struct SegT {
const int MX = 1e9 + 5;
vector<Node> st;
int pt = 0;
int create_node() {
st.pb(Node());
return pt++;
}
void reset() {
pt = 0;
st.clear();
create_node();
}
void extend(int v) {
if(st[v].lc == -1) st[v].lc = create_node();
if(st[v].rc == -1) st[v].rc = create_node();
}
void push(int v) {
st[st[v].lc].mn += st[v].tag;
st[st[v].lc].mx += st[v].tag;
st[st[v].lc].tag += st[v].tag;
st[st[v].rc].mn += st[v].tag;
st[st[v].rc].mx += st[v].tag;
st[st[v].rc].tag += st[v].tag;
st[v].tag = 0;
}
void update(int tl, int tr, int v, int l, int r, int val) {
if(tl >= l && tr <= r) {
st[v].mn += val;
st[v].mx += val;
st[v].tag += val;
return;
}
if(tl > r || tr < l) {
return;
}
int tm = (tl + tr) >> 1;
extend(v); push(v);
update(tl, tm, st[v].lc, l, r, val);
update(tm + 1, tr, st[v].rc, l, r, val);
st[v].mn = min(st[st[v].lc].mn, st[st[v].rc].mn);
st[v].mx = max(st[st[v].lc].mx, st[st[v].rc].mx);
}
int get_ind(int tl, int tr, int v, int r) {
if(tr <= r) {
return st[v].sum;
}
if(tl > r) return 0;
int tm = (tl + tr) >> 1;
extend(v); push(v);
return get_ind(tl, tm, st[v].lc, r) + get_ind(tm + 1, tr, st[v].rc, r);
}
void ins(int tl, int tr, int v, int ind, int val) {
if(tl == tr) {
st[v].sum++;
st[v].mn = min(st[v].mn, val);
st[v].mx = max(st[v].mx, val);
return;
}
int tm = (tl + tr) >> 1;
extend(v); push(v);
if(ind <= tm) {
ins(tl, tm, st[v].lc, ind, val);
}
else {
ins(tm + 1, tr, st[v].rc, ind, val);
}
st[v].mn = min(st[st[v].lc].mn, st[st[v].rc].mn);
st[v].mx = max(st[st[v].lc].mx, st[st[v].rc].mx);
st[v].sum = st[st[v].lc].sum + st[st[v].rc].sum;
}
int query_mx(int tl, int tr, int v, int r) {
if(tr <= r) {
return st[v].mx;
}
if(tl > r) return -INF;
int tm = (tl + tr) >> 1;
extend(v); push(v);
return max(query_mx(tl, tm, st[v].lc, r), query_mx(tm + 1, tr, st[v].rc, r));
}
int query_mn(int tl, int tr, int v, int l) {
if(tl >= l) {
return st[v].mn;
}
if(l > tr) {
return INF;
}
int tm = (tl + tr) >> 1;
extend(v); push(v);
return min(query_mn(tl, tm, st[v].lc, l), query_mn(tm + 1, tr, st[v].rc, l));
}
int insert(int ind) {
int i = get_ind(0, MX, 0, ind);
int val = ind - i * D;
// cout << "ind:" << ind << " i:" << i << "val:" << val << "\n";
ins(0, MX, 0, ind, val);
update(0, MX, 0, ind + 1, MX, -D);
// cout << "mx:" << query_mx(0, MX, 0, ind) << "\n";
// cout << "mn:" << query_mn(0, MX, 0, ind) << "\n";
int ret = query_mx(0, MX, 0, ind) - query_mn(0, MX, 0, ind);
return max(0ll, ret);
}
};
SegT st;
void solve() {
int n, m;
cin >> n >> m >> D;
st.reset();
if(n > 0) {
REP(i, n) {
int a;
cin >> a;
st.insert(a);
}
}
REP(i, m) {
int b;
cin >> b;
int ret = st.insert(b);
if(ret & 1) {
cout << ret / 2;
cout << ".5 ";
}
else {
cout << ret / 2 << " ";
}
}
cout << "\n";
}
signed main() {
fastio();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
629 ms |
396816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
629 ms |
396816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
