oj.uz

Submission #1009720

# Submission time Handle Problem Language Result Execution time Memory
1009720 2024-06-28T01:04:41 Z Cookie Measures (CEOI22_measures) C++14
100 / 100
 299 ms 26252 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
const int cox[4] = {1, 0, -1, 0};
const int coy[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7, pr = 31;
const int mxn = 4e5 + 5, mxd = 250 * 250, sq = 500, mxv = 2e6 + 1;
const int max_iter = 8e4, global_iter = 15e5 + 5;
//const int base = (1 <<18);
const ll inf = 1e16 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
int n, m, d;
ll lz[4 * mxn + 1], mx[4 * mxn + 1], mn[4 * mxn + 1], a[mxn + 1];
int bit[mxn + 1];
ll ans = 0;
void pull(int nd){
    mx[nd] = max(mx[nd << 1], mx[nd << 1 | 1]);
    mn[nd] = min(mn[nd << 1], mn[nd << 1 | 1]);
}
void go(int nd, ll v){
    lz[nd] += v; mx[nd] += v; mn[nd] += v;
}
void push(int nd){
    ll &v = lz[nd];
    go(nd << 1, v); go(nd << 1 | 1, v);
    v = 0;
}
void updadd(int nd, int l, int r, int ql, int qr, ll v){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        //cout << l << " " << r << " " << v <<  "\n";
        go(nd, v);
        return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    updadd(nd << 1, l, mid, ql, qr, v); updadd(nd << 1 | 1, mid + 1, r, ql, qr, v);
    pull(nd);
}
void updset(int nd, int l, int r, int id, ll v){
    if(l == r){
        //cout << l << " " << v << "\n";
        mx[nd] = mn[nd] = v; return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    if(id <= mid)updset(nd << 1, l, mid, id, v);
    else updset(nd << 1 | 1, mid + 1, r, id, v);
    pull(nd);
    //cout << l << " " << r << " " << mx[nd] << "\n";
}
ll getmx(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(-inf);
    if(ql <= l && qr >= r)return(mx[nd]);
    int mid = (l + r) >> 1;
    push(nd);
    return(max(getmx(nd << 1, l, mid, ql, qr), getmx(nd << 1 | 1, mid + 1, r, ql, qr)));
}
ll getmn(int nd, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(inf);
    if(ql <= l && qr >= r)return(mn[nd]);
    int mid = (l + r) >> 1;
    push(nd);
    return(min(getmn(nd << 1, l, mid, ql, qr), getmn(nd << 1 | 1, mid + 1, r, ql, qr)));
}
vt<pii>comp;
void upd(int p, int v){
    while(p <= sz(comp)){
        bit[p] += v; p += p & (-p);
    }
}
int get(int p){
    int ans = 0;
    while(p){
        ans += bit[p]; p -= p & (-p);
    }
    return(ans);
}
void add(pii curr){
    int id = lower_bound(ALL(comp), curr) - comp.begin() + 1;
    ll kth = get(id - 1) + 1;
    updadd(1, 1, sz(comp), id + 1, sz(comp), d);
    upd(id, 1); 
    updset(1, 1, sz(comp), id, kth * d - curr.fi);
    ans = max(ans, getmx(1, 1, sz(comp), id, sz(comp)) - getmn(1, 1, sz(comp), 1, id));
}
void solve(){
    cin >> n >> m >> d;
    for(int i = 1; i <= 4 * (n + m); i++){
        mx[i] = -inf; mn[i] = inf;
    }
    for(int i = 1; i <= n + m; i++){
        cin >> a[i]; comp.pb(mpp(a[i], i));
    }
    sort(ALL(comp)); 
    for(int i = 1; i <= n + m; i++){
        add(mpp(a[i], i));
        //cout << ans << ' ';
        if(i > n){
            if(ans % 2 == 0)cout << ans / 2 << " ";
            else cout << fixed << setprecision(1) << ans / 2.0 << " ";
        }
    }
}
 
 
 
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("KHONG.inp", "r", stdin);
    //freopen("KHONG.out", "w", stdout);
    int tt; tt = 1;
    while(tt--)solve();
    return(0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 680 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 680 KB Output is correct
9 Correct 220 ms 22988 KB Output is correct
10 Correct 209 ms 23240 KB Output is correct
11 Correct 139 ms 22984 KB Output is correct
12 Correct 170 ms 22980 KB Output is correct
13 Correct 141 ms 22728 KB Output is correct
14 Correct 152 ms 23056 KB Output is correct
15 Correct 208 ms 22284 KB Output is correct
16 Correct 144 ms 23064 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 23944 KB Output is correct
2 Correct 228 ms 26052 KB Output is correct
3 Correct 207 ms 25916 KB Output is correct
4 Correct 158 ms 23748 KB Output is correct
5 Correct 170 ms 25028 KB Output is correct
6 Correct 170 ms 24008 KB Output is correct
7 Correct 206 ms 25028 KB Output is correct
8 Correct 190 ms 23748 KB Output is correct
9 Correct 204 ms 23832 KB Output is correct
10 Correct 189 ms 26092 KB Output is correct
11 Correct 211 ms 24548 KB Output is correct
12 Correct 191 ms 25540 KB Output is correct
13 Correct 183 ms 23752 KB Output is correct
14 Correct 169 ms 25800 KB Output is correct
15 Correct 193 ms 25620 KB Output is correct
16 Correct 187 ms 23236 KB Output is correct
17 Correct 173 ms 25044 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 23944 KB Output is correct
2 Correct 228 ms 26052 KB Output is correct
3 Correct 207 ms 25916 KB Output is correct
4 Correct 158 ms 23748 KB Output is correct
5 Correct 170 ms 25028 KB Output is correct
6 Correct 170 ms 24008 KB Output is correct
7 Correct 206 ms 25028 KB Output is correct
8 Correct 190 ms 23748 KB Output is correct
9 Correct 204 ms 23832 KB Output is correct
10 Correct 189 ms 26092 KB Output is correct
11 Correct 211 ms 24548 KB Output is correct
12 Correct 191 ms 25540 KB Output is correct
13 Correct 183 ms 23752 KB Output is correct
14 Correct 169 ms 25800 KB Output is correct
15 Correct 193 ms 25620 KB Output is correct
16 Correct 187 ms 23236 KB Output is correct
17 Correct 173 ms 25044 KB Output is correct
18 Correct 261 ms 24264 KB Output is correct
19 Correct 239 ms 25800 KB Output is correct
20 Correct 195 ms 25880 KB Output is correct
21 Correct 194 ms 24008 KB Output is correct
22 Correct 226 ms 24132 KB Output is correct
23 Correct 167 ms 24020 KB Output is correct
24 Correct 252 ms 24516 KB Output is correct
25 Correct 176 ms 23648 KB Output is correct
26 Correct 267 ms 23752 KB Output is correct
27 Correct 299 ms 26252 KB Output is correct
28 Correct 180 ms 24088 KB Output is correct
29 Correct 252 ms 25568 KB Output is correct
30 Correct 196 ms 23588 KB Output is correct
31 Correct 197 ms 25800 KB Output is correct
32 Correct 202 ms 25576 KB Output is correct
33 Correct 271 ms 23260 KB Output is correct
34 Correct 202 ms 25032 KB Output is correct