oj.uz

Submission #1102793

# Submission time Handle Problem Language Result Execution time Memory
1102793 2024-10-18T23:35:41 Z vladilius Measures (CEOI22_measures) C++17
45 / 100
 500 ms 40024 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, int>> t;
    int n;
    ST(int ns){
        n = ns;
        t.resize(4 * n);
    }
    void upd(int v, int tl, int tr, int& p, ll& x, ll s){
        if (tl == tr){
            t[v].ss = 1;
            t[v].ff = x - s;
            return;
        }
        s += t[v].ff;
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            upd(vv, tl, tm, p, x, s);
        }
        else {
            upd(vv + 1, tm + 1, tr, p, x, s);
        }
        t[v].ss = t[vv].ss + t[vv + 1].ss;
    }
    void upd(int p, ll x){
        upd(1, 1, n, p, x, 0);
    }
    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;
            return;
        }
        int tm = (tl + tr) / 2, vv = 2 * v;
        add(vv, tl, tm, l, r, x);
        add(vv + 1, tm + 1, tr, l, r, x);
    }
    void add(int l, int r, int x){
        add(1, 1, n, l, r, x);
    }
    ll get1(int v, int tl, int tr, int& p){
        if (tl == tr) return t[v].ff;
        int tm = (tl + tr) / 2, vv = 2 * v;
        if (p <= tm){
            return t[v].ff + get1(vv, tl, tm, p);
        }
        return t[v].ff + get1(vv + 1, tm + 1, tr, p);
    }
    ll get1(int p){
        return get1(1, 1, n, p);
    }
    int get2(int v, int tl, int tr, int& p){
        if (tl > p) return 0;
        if (tr <= p) return t[v].ss;
        int tm = (tl + tr) / 2, vv = 2 * v;
        return get2(vv, tl, tm, p) + get2(vv + 1, tm + 1, tr, p);
    }
    int get2(int p){
        return get2(1, 1, n, p);;
    }
};
 
struct ST1{
    vector<ll> t;
    vector<ll> p;
    int n;
    ST1(int ns){
        n = ns;
        t.assign(4 * n, -inf);
        p.assign(4 * n, 0);
    }
    void upd(int v, int tl, int tr, int& p, ll& x){
        if (tl == tr){
            t[v] = x;
            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] = max(t[vv], t[vv + 1]);
    }
    void upd(int p, ll x){
        upd(1, 1, n, p, x);
    }
    void push(int& v){
        if (!p[v]) return;
        int vv = 2 * v;
        t[vv] += p[v]; t[vv + 1] += p[v];
        p[vv] += p[v]; p[vv + 1] += p[v];
        p[v] = 0;
    }
    void add(int v, int tl, int tr, int& l, int& r, ll& x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            t[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] = max(t[vv], t[vv + 1]);
    }
    void add(int l, int r, ll x){
        add(1, 1, n, l, r, x);
    }
    ll get(){
        return t[1];
    }
};
 
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)
    
    int N = (int) all.size() - 1;
    ST T(N); ST1 T1(N);
    int cc = 0;
    vector<int> r(N + 1);
    set<int> st;
    auto add = [&](int x){
        cc++;
        int i = p[cc];
        ll vi = x - 1LL * d * (T.get2(i) + 1);
        T.upd(i, vi);
        T.add(i + 1, N, -d);
 
        auto it = st.lower_bound(i);
        if (it != st.begin()){
            int j = *prev(it);
            ll vj = T.get1(j);
            T1.add(i + 1, N, d);
            T1.add(max(i, r[j]) + 1, N, -d);
            if (vj >= vi){
                while (true){
                    auto it1 = st.upper_bound(j);
                    if (it1 == st.end()) break;
                    int k = *it1;
                    if (T.get1(k) <= vj){
                        r[j] = r[k];
                        T1.add(k, r[k], all[j].ff - all[k].ff + 1LL * d * (T.get2(k) - T.get2(j)));
                        st.erase(it1);
                        continue;
                    }
                    break;
                }
                T1.upd(i, all[j].ff - x + 1LL * d * (T.get2(i) - T.get2(j)));
                r[j] = max(r[j], i);
                return;
            }
            T1.add(i + 1, r[j], x - all[j].ff);
            r[i] = r[j];
            r[j] = i - 1;
        }
        
        T1.upd(i, 0);
        r[i] = max(r[i], i);
        while (true){
            it = st.lower_bound(i);
            if (it == st.end()) break;
            int k = *it;
            if (T.get1(k) <= vi){
                r[i] = r[k];
                T1.add(k, r[k], x - all[k].ff + 1LL * d * (T.get2(k) - T.get2(i)));
                st.erase(it);
                continue;
            }
            break;
        }
        st.insert(i);
    };
    
    for (int i = 1; i <= n; i++){
        add(a[i]);
    }
    
    for (int i = 1; i <= m; i++){
        add(b[i]);
        print(T1.get());
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:154: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]
  154 |     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 3 ms 760 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 3 ms 592 KB Output is correct
7 Correct 4 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 3 ms 760 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 3 ms 592 KB Output is correct
7 Correct 4 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Incorrect 500 ms 39144 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 37824 KB Output is correct
2 Correct 187 ms 32704 KB Output is correct
3 Correct 183 ms 32608 KB Output is correct
4 Correct 261 ms 39664 KB Output is correct
5 Correct 179 ms 31936 KB Output is correct
6 Correct 241 ms 38480 KB Output is correct
7 Correct 190 ms 31980 KB Output is correct
8 Correct 273 ms 39880 KB Output is correct
9 Correct 269 ms 39940 KB Output is correct
10 Correct 179 ms 32960 KB Output is correct
11 Correct 258 ms 39876 KB Output is correct
12 Correct 172 ms 32448 KB Output is correct
13 Correct 243 ms 40024 KB Output is correct
14 Correct 172 ms 32448 KB Output is correct
15 Correct 177 ms 32388 KB Output is correct
16 Correct 156 ms 30720 KB Output is correct
17 Correct 180 ms 31936 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 37824 KB Output is correct
2 Correct 187 ms 32704 KB Output is correct
3 Correct 183 ms 32608 KB Output is correct
4 Correct 261 ms 39664 KB Output is correct
5 Correct 179 ms 31936 KB Output is correct
6 Correct 241 ms 38480 KB Output is correct
7 Correct 190 ms 31980 KB Output is correct
8 Correct 273 ms 39880 KB Output is correct
9 Correct 269 ms 39940 KB Output is correct
10 Correct 179 ms 32960 KB Output is correct
11 Correct 258 ms 39876 KB Output is correct
12 Correct 172 ms 32448 KB Output is correct
13 Correct 243 ms 40024 KB Output is correct
14 Correct 172 ms 32448 KB Output is correct
15 Correct 177 ms 32388 KB Output is correct
16 Correct 156 ms 30720 KB Output is correct
17 Correct 180 ms 31936 KB Output is correct
18 Incorrect 452 ms 37828 KB Output isn't correct
19 Halted 0 ms 0 KB -