oj.uz

Submission #1102797

# Submission time Handle Problem Language Result Execution time Memory
1102797 2024-10-19T00:04:01 Z vladilius Measures (CEOI22_measures) C++17
45 / 100
 302 ms 29632 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e15;

struct ST{
    vector<pair<ll, ll>> t;
    vector<ll> p;
    vector<int> b;
    int n;
    ST(int ns){
        n = ns;
        t.assign(4 * n, {-inf, inf});
        p.resize(4 * n);
        b.resize(4 * n);
    }
    void push(int& v){
        if (!p[v]) return;
        int vv = 2 * v;
        t[vv].ff += p[v]; t[vv].ss += p[v];
        t[vv + 1].ff += p[v]; t[vv + 1].ss += p[v];
        p[vv] += p[v]; p[vv + 1] += p[v];
        p[v] = 0;
    }
    void upd(int v, int tl, int tr, int& p, ll& x){
        if (tl == tr){
            t[v] = {x, x};
            b[v] = 1;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v);
        if (p <= tm){
            upd(vv, tl, tm, p, x);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, x);
        }
        t[v].ff = max(t[vv].ff, t[vv + 1].ff);
        t[v].ss = min(t[vv].ss, t[vv + 1].ss);
        b[v] = b[vv] + b[vv + 1];
    }
    void upd(int p, ll x){
        upd(1, 1, n, p, x);
    }
    int get(int v, int tl, int tr, int& p){
        if (tl > p) return 0;
        if (tr <= p) return b[v];
        int tm = (tl + tr) / 2, vv = 2 * v;
        return get(vv, tl, tm, p) + get(vv + 1, tm + 1, tr, p);
    }
    int get(int p){
        return get(1, 1, n, p);
    }
    void add(int v, int tl, int tr, int& l, int& r, int& x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            t[v].ff += x;
            t[v].ss += x;
            p[v] += x;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v);
        add(vv, tl, tm, l, r, x);
        add(vv + 1, tm + 1, tr, l, r, x);
        t[v].ff = max(t[vv].ff, t[vv + 1].ff);
        t[v].ss = min(t[vv].ss, t[vv + 1].ss);
    }
    void add(int l, int r, int x){
        add(1, 1, n, l, r, x);
    }
    ll mx(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return -inf;
        if (l <= tl && tr <= r) return t[v].ff;
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v);
        return max(mx(vv, tl, tm, l, r), mx(vv + 1, tm + 1, tr, l, r));
    }
    ll mx(int l, int r){
        return mx(1, 1, n, l, r);
    }
    ll mn(int v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return inf;
        if (l <= tl && tr <= r) return t[v].ss;
        int tm = (tl + tr) / 2, vv = 2 * v;
        push(v);
        return min(mn(vv, tl, tm, l, r), mn(vv + 1, tm + 1, tr, l, r));
    }
    ll mn(int l, int r){
        return mn(1, 1, n, l, r);
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cout<<fixed<<setprecision(15);
    auto print = [&](ll x){
        if (x % 2 == 0){
            cout<<x / 2<<" ";
        }
        else {
            cout<<(x - 1) / 2<<".5 ";
        }
    };
    
    int n, m, d; cin>>n>>m>>d;
    vector<int> a(n + 1), b(m + 1);
    vector<pii> all = {{0, 0}};
    for (int i = 1; i <= n; i++){
        cin>>a[i];
        all.pb({a[i], i});
    }
    for (int i = 1; i <= m; i++){
        cin>>b[i];
        all.pb({b[i], i + n});
    }
    
    sort(all.begin(), all.end());
    vector<int> p(all.size());
    for (int i = 1; i < all.size(); i++) p[all[i].ss] = i;
    
    // f[i] = x[i] - d * i
    // t[i] = x[j] - x[i] + d * (i - j) = f[j] - f[i]
    
    int N = (int) all.size() - 1, cc = 0;
    ll out = 0;
    ST T(N);
    auto add = [&](int x){
        cc++;
        int i = p[cc];
        ll v = x - 1LL * d * (T.get(i) + 1);
        T.upd(i, v);
        T.add(i + 1, N, -d);
        
        ll v1 = T.mx(1, i - 1), v2 = T.mn(i, N);
        out = max(out, v1 - v2);
    };
    
    for (int i = 1; i <= n; i++){
        add(a[i]);
    }
    
    for (int i = 1; i <= m; i++){
        add(b[i]);
        print(out);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int i = 1; i < all.size(); i++) p[all[i].ss] = i;
      |                     ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 732 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 3 ms 736 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 239 ms 25812 KB Output is correct
10 Correct 213 ms 25808 KB Output is correct
11 Correct 161 ms 25804 KB Output is correct
12 Correct 181 ms 25812 KB Output is correct
13 Correct 152 ms 25964 KB Output is correct
14 Incorrect 149 ms 26836 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 26840 KB Output is correct
2 Correct 153 ms 28776 KB Output is correct
3 Correct 160 ms 28868 KB Output is correct
4 Correct 154 ms 26560 KB Output is correct
5 Correct 157 ms 27840 KB Output is correct
6 Correct 152 ms 27024 KB Output is correct
7 Correct 154 ms 28096 KB Output is correct
8 Correct 157 ms 26816 KB Output is correct
9 Correct 147 ms 26556 KB Output is correct
10 Correct 165 ms 29632 KB Output is correct
11 Correct 174 ms 27584 KB Output is correct
12 Correct 156 ms 28424 KB Output is correct
13 Correct 155 ms 26628 KB Output is correct
14 Correct 162 ms 28608 KB Output is correct
15 Correct 161 ms 28376 KB Output is correct
16 Correct 150 ms 26560 KB Output is correct
17 Correct 153 ms 29216 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 26840 KB Output is correct
2 Correct 153 ms 28776 KB Output is correct
3 Correct 160 ms 28868 KB Output is correct
4 Correct 154 ms 26560 KB Output is correct
5 Correct 157 ms 27840 KB Output is correct
6 Correct 152 ms 27024 KB Output is correct
7 Correct 154 ms 28096 KB Output is correct
8 Correct 157 ms 26816 KB Output is correct
9 Correct 147 ms 26556 KB Output is correct
10 Correct 165 ms 29632 KB Output is correct
11 Correct 174 ms 27584 KB Output is correct
12 Correct 156 ms 28424 KB Output is correct
13 Correct 155 ms 26628 KB Output is correct
14 Correct 162 ms 28608 KB Output is correct
15 Correct 161 ms 28376 KB Output is correct
16 Correct 150 ms 26560 KB Output is correct
17 Correct 153 ms 29216 KB Output is correct
18 Incorrect 302 ms 27072 KB Output isn't correct
19 Halted 0 ms 0 KB -