#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const ll NMAX = 400001;
const int INF = (1 << 29);
const ll nrbits = 20;
const ll MOD = 998244353;
const int VMAX = 10;
int d, cnt;
int lazy[NMAX * 4];
vector <pii> tot;
struct elem{
int val, nrm;
}a[NMAX], b[NMAX];
bool cmp(pii aa, pii bb){
int prim = a[aa.first].val;
if(aa.second == 1)
prim = b[aa.first].val;
int sec = a[bb.first].val;
if(bb.second == 1)
sec = b[bb.first].val;
return prim < sec;
}
struct Node {
int maxim, minim;
int sol;
} aint[NMAX * 4];
void propaga(int node, int st, int dr) {
if(st != dr) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
aint[node].maxim += lazy[node];
aint[node].minim += lazy[node];
lazy[node] = 0;
}
Node combine(Node a, Node b) {
Node sol = {-INF, INF, 0};
sol.sol = max(a.sol, b.sol);
sol.sol = max(sol.sol, a.maxim - b.minim);
sol.maxim = max(a.maxim, b.maxim);
sol.minim = min(a.minim, b.minim);
return sol;
}
void activate(int node, int st, int dr, int x, int val) {
propaga(node, st, dr);
if(st == dr) {
aint[node].maxim += INF + val;
aint[node].minim -= INF;
aint[node].minim += val;
aint[node].sol = 0;
return;
}
int mid = (st + dr) / 2;
if(x <= mid)
activate(node * 2, st, mid, x, val);
else
activate(node * 2 + 1, mid + 1, dr, x, val);
propaga(node * 2, st, mid);
propaga(node * 2 + 1, mid + 1, dr);
aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}
void update(int node, int st, int dr, int a, int b, int val) {
if(a > dr)
return;
propaga(node, st, dr);
if(a <= st && dr <= b) {
lazy[node] += val;
return;
}
int mid = (st + dr) / 2;
if(a <= mid)
update(node * 2, st, mid, a, b, val);
if(b > mid)
update(node * 2 + 1, mid + 1, dr, a, b, val);
propaga(node * 2, st, mid);
propaga(node * 2 + 1, mid + 1, dr);
aint[node] = combine(aint[node * 2], aint[node * 2 + 1]);
}
signed main() {
#ifdef HOME
ifstream cin(".in");
ofstream cout(".out");
#endif // HOME
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
for(int i = 0; i < NMAX * 4; i++) {
aint[i].maxim = -INF;
aint[i].minim = INF;
aint[i].sol = 0;
}
int n, i, m, x;
cin >> n >> m >> d;
tot.clear();
for(i = 1; i <= n; i++) {
cin >> a[i].val;
tot.push_back({i, 0});
}
for(i = 1; i <= m; i++) {
cin >> b[i].val;
tot.push_back({i, 1});
}
sort(tot.begin(), tot.end(), cmp);
for(int i = 0; i < tot.size(); i++){
if(tot[i].second == 1){
b[tot[i].first].nrm = i + 1;
}else{
a[tot[i].first].nrm = i + 1;
}
}
cnt = tot.size();
for(i = 1; i <= n; i++) {
update(1, 1, cnt, a[i].nrm + 1, cnt, -d);
activate(1, 1, cnt, a[i].nrm, a[i].val);
}
for(i = 1; i <= m; i++) {
update(1, 1, cnt, b[i].nrm + 1, cnt, -d);
activate(1, 1, cnt, b[i].nrm, b[i].val);
propaga(1, 1, cnt);
int sol = max(0, aint[1].sol);
cout << sol/2;
if(sol%2) cout << ".5";
cout << " ";
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int i = 0; i < tot.size(); i++){
| ~~^~~~~~~~~~~~
Main.cpp:108:18: warning: unused variable 'x' [-Wunused-variable]
108 | int n, i, m, x;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
227 ms |
28412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
227 ms |
28412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
