oj.uz

Submission #1102798

# Submission time Handle Problem Language Result Execution time Memory
1102798 2024-10-19T00:04:39 Z vladilius Measures (CEOI22_measures) C++17
45 / 100
 263 ms 29120 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 = 1e17;

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 592 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 3 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 247 ms 25960 KB Output is correct
10 Correct 217 ms 25792 KB Output is correct
11 Correct 144 ms 25800 KB Output is correct
12 Correct 181 ms 25792 KB Output is correct
13 Correct 132 ms 25800 KB Output is correct
14 Incorrect 145 ms 25960 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 155 ms 27072 KB Output is correct
2 Correct 174 ms 28864 KB Output is correct
3 Correct 152 ms 28732 KB Output is correct
4 Correct 157 ms 26600 KB Output is correct
5 Correct 188 ms 27840 KB Output is correct
6 Correct 157 ms 27104 KB Output is correct
7 Correct 156 ms 28104 KB Output is correct
8 Correct 155 ms 26816 KB Output is correct
9 Correct 153 ms 26728 KB Output is correct
10 Correct 162 ms 29120 KB Output is correct
11 Correct 159 ms 27408 KB Output is correct
12 Correct 159 ms 28352 KB Output is correct
13 Correct 149 ms 26824 KB Output is correct
14 Correct 158 ms 28608 KB Output is correct
15 Correct 164 ms 28352 KB Output is correct
16 Correct 150 ms 26812 KB Output is correct
17 Correct 151 ms 28096 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 27072 KB Output is correct
2 Correct 174 ms 28864 KB Output is correct
3 Correct 152 ms 28732 KB Output is correct
4 Correct 157 ms 26600 KB Output is correct
5 Correct 188 ms 27840 KB Output is correct
6 Correct 157 ms 27104 KB Output is correct
7 Correct 156 ms 28104 KB Output is correct
8 Correct 155 ms 26816 KB Output is correct
9 Correct 153 ms 26728 KB Output is correct
10 Correct 162 ms 29120 KB Output is correct
11 Correct 159 ms 27408 KB Output is correct
12 Correct 159 ms 28352 KB Output is correct
13 Correct 149 ms 26824 KB Output is correct
14 Correct 158 ms 28608 KB Output is correct
15 Correct 164 ms 28352 KB Output is correct
16 Correct 150 ms 26812 KB Output is correct
17 Correct 151 ms 28096 KB Output is correct
18 Incorrect 263 ms 27072 KB Output isn't correct
19 Halted 0 ms 0 KB -