# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
700218 |
2023-02-19T01:11:15 Z |
Lobo |
Measures (CEOI22_measures) |
C++17 |
|
505 ms |
28332 KB |
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 4e5+10;
int n, m, d;
int trmn[4*maxn], trmx[4*maxn], lzmn[4*maxn], lzmx[4*maxn];
void flush(int no, int l, int r) {
trmn[no]+= lzmn[no];
trmx[no]+= lzmx[no];
if(l != r) {
int lc=2*no,rc=2*no+1;
lzmn[lc]+= lzmn[no];
lzmn[rc]+= lzmn[no];
lzmx[lc]+= lzmx[no];
lzmx[rc]+= lzmx[no];
}
lzmn[no] = 0;
lzmx[no] = 0;
}
void updmn(int no, int l, int r, int L, int R, int val) {
flush(no,l,r);
if(l > R || r < L) return;
if(l >= L && r <= R) {
lzmn[no] = val;
flush(no,l,r);
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
updmn(lc,l,mid,L,R,val);
updmn(rc,mid+1,r,L,R,val);
trmn[no] = min(trmn[lc],trmn[rc]);
}
void updmx(int no, int l, int r, int L, int R, int val) {
flush(no,l,r);
if(l > R || r < L) return;
if(l >= L && r <= R) {
lzmx[no] = val;
flush(no,l,r);
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
updmx(lc,l,mid,L,R,val);
updmx(rc,mid+1,r,L,R,val);
trmx[no] = max(trmx[lc],trmx[rc]);
}
int qrymn(int no, int l, int r, int L, int R) {
flush(no,l,r);
if(l > R || r < L) return inf;
if(l >= L && r <= R) return trmn[no];
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
return min(qrymn(lc,l,mid,L,R),qrymn(rc,mid+1,r,L,R));
}
int qrymx(int no, int l, int r, int L, int R) {
flush(no,l,r);
if(l > R || r < L) return -inf;
if(l >= L && r <= R) return trmx[no];
int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
return max(qrymx(lc,l,mid,L,R),qrymx(rc,mid+1,r,L,R));
}
void solve() {
cin >> n >> m >> d;
int ans = 0;
vector<pair<int,int>> qr,cc;
for(int i = 1; i <= n+m; i++) {
int x; cin >> x;
qr.pb(mp(x,i));
cc.pb(mp(x,i));
}
sort(all(cc));
updmx(1,1,n+m,1,n+m,-inf);
updmn(1,1,n+m,1,n+m,+inf);
for(int i = 1; i <= n+m; i++) {
int x = qr[i-1].fr;
int id = upper_bound(all(cc),mp(x,i))-cc.begin();
updmx(1,1,n+m,id,id,+inf+x);
updmn(1,1,n+m,id,id,-inf+x);
updmx(1,1,n+m,id,n+m,-d);
updmn(1,1,n+m,id,n+m,-d);
ans = max(ans, -qrymn(1,1,n+m,id,n+m)+qrymx(1,1,n+m,1,id));
if(i > n) {
cout << ans/2;
if(ans%2 == 1) cout << ".5 ";
else cout << " ";
}
}
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
4 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
7 |
Correct |
3 ms |
592 KB |
Output is correct |
8 |
Correct |
3 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
596 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
4 ms |
468 KB |
Output is correct |
4 |
Correct |
3 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
468 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
7 |
Correct |
3 ms |
592 KB |
Output is correct |
8 |
Correct |
3 ms |
468 KB |
Output is correct |
9 |
Correct |
478 ms |
25116 KB |
Output is correct |
10 |
Correct |
469 ms |
25124 KB |
Output is correct |
11 |
Correct |
351 ms |
25164 KB |
Output is correct |
12 |
Correct |
376 ms |
25164 KB |
Output is correct |
13 |
Correct |
355 ms |
24680 KB |
Output is correct |
14 |
Correct |
359 ms |
25312 KB |
Output is correct |
15 |
Correct |
473 ms |
24460 KB |
Output is correct |
16 |
Correct |
352 ms |
25252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
366 ms |
26200 KB |
Output is correct |
2 |
Correct |
378 ms |
28320 KB |
Output is correct |
3 |
Correct |
388 ms |
28076 KB |
Output is correct |
4 |
Correct |
375 ms |
26196 KB |
Output is correct |
5 |
Correct |
389 ms |
27256 KB |
Output is correct |
6 |
Correct |
363 ms |
26268 KB |
Output is correct |
7 |
Correct |
374 ms |
27352 KB |
Output is correct |
8 |
Correct |
366 ms |
25960 KB |
Output is correct |
9 |
Correct |
380 ms |
25900 KB |
Output is correct |
10 |
Correct |
365 ms |
28316 KB |
Output is correct |
11 |
Correct |
371 ms |
26740 KB |
Output is correct |
12 |
Correct |
366 ms |
27680 KB |
Output is correct |
13 |
Correct |
368 ms |
25920 KB |
Output is correct |
14 |
Correct |
364 ms |
27936 KB |
Output is correct |
15 |
Correct |
372 ms |
27848 KB |
Output is correct |
16 |
Correct |
362 ms |
25476 KB |
Output is correct |
17 |
Correct |
378 ms |
27216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
366 ms |
26200 KB |
Output is correct |
2 |
Correct |
378 ms |
28320 KB |
Output is correct |
3 |
Correct |
388 ms |
28076 KB |
Output is correct |
4 |
Correct |
375 ms |
26196 KB |
Output is correct |
5 |
Correct |
389 ms |
27256 KB |
Output is correct |
6 |
Correct |
363 ms |
26268 KB |
Output is correct |
7 |
Correct |
374 ms |
27352 KB |
Output is correct |
8 |
Correct |
366 ms |
25960 KB |
Output is correct |
9 |
Correct |
380 ms |
25900 KB |
Output is correct |
10 |
Correct |
365 ms |
28316 KB |
Output is correct |
11 |
Correct |
371 ms |
26740 KB |
Output is correct |
12 |
Correct |
366 ms |
27680 KB |
Output is correct |
13 |
Correct |
368 ms |
25920 KB |
Output is correct |
14 |
Correct |
364 ms |
27936 KB |
Output is correct |
15 |
Correct |
372 ms |
27848 KB |
Output is correct |
16 |
Correct |
362 ms |
25476 KB |
Output is correct |
17 |
Correct |
378 ms |
27216 KB |
Output is correct |
18 |
Correct |
503 ms |
26332 KB |
Output is correct |
19 |
Correct |
502 ms |
28056 KB |
Output is correct |
20 |
Correct |
379 ms |
28060 KB |
Output is correct |
21 |
Correct |
411 ms |
26224 KB |
Output is correct |
22 |
Correct |
433 ms |
26384 KB |
Output is correct |
23 |
Correct |
377 ms |
26312 KB |
Output is correct |
24 |
Correct |
505 ms |
26880 KB |
Output is correct |
25 |
Correct |
364 ms |
25864 KB |
Output is correct |
26 |
Correct |
490 ms |
25864 KB |
Output is correct |
27 |
Correct |
492 ms |
28332 KB |
Output is correct |
28 |
Correct |
432 ms |
26320 KB |
Output is correct |
29 |
Correct |
468 ms |
27664 KB |
Output is correct |
30 |
Correct |
389 ms |
25924 KB |
Output is correct |
31 |
Correct |
392 ms |
27924 KB |
Output is correct |
32 |
Correct |
395 ms |
27680 KB |
Output is correct |
33 |
Correct |
485 ms |
25500 KB |
Output is correct |
34 |
Correct |
396 ms |
27344 KB |
Output is correct |