oj.uz

Submission #1102794

# Submission time Handle Problem Language Result Execution time Memory
1102794 2024-10-18T23:37:18 Z vladilius Measures (CEOI22_measures) C++17
100 / 100
 576 ms 41984 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;
            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] = 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:155: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]
  155 |     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 848 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 3 ms 592 KB Output is correct
5 Correct 2 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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 848 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 3 ms 592 KB Output is correct
5 Correct 2 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 521 ms 38848 KB Output is correct
10 Correct 293 ms 29888 KB Output is correct
11 Correct 158 ms 29896 KB Output is correct
12 Correct 240 ms 31168 KB Output is correct
13 Correct 159 ms 30772 KB Output is correct
14 Correct 282 ms 39104 KB Output is correct
15 Correct 516 ms 32256 KB Output is correct
16 Correct 157 ms 29896 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 37780 KB Output is correct
2 Correct 197 ms 32832 KB Output is correct
3 Correct 194 ms 32644 KB Output is correct
4 Correct 260 ms 39708 KB Output is correct
5 Correct 173 ms 31936 KB Output is correct
6 Correct 268 ms 38336 KB Output is correct
7 Correct 181 ms 32000 KB Output is correct
8 Correct 275 ms 40036 KB Output is correct
9 Correct 259 ms 39872 KB Output is correct
10 Correct 187 ms 33096 KB Output is correct
11 Correct 262 ms 39872 KB Output is correct
12 Correct 180 ms 32476 KB Output is correct
13 Correct 273 ms 39872 KB Output is correct
14 Correct 178 ms 32448 KB Output is correct
15 Correct 189 ms 32448 KB Output is correct
16 Correct 173 ms 30656 KB Output is correct
17 Correct 174 ms 31784 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 37780 KB Output is correct
2 Correct 197 ms 32832 KB Output is correct
3 Correct 194 ms 32644 KB Output is correct
4 Correct 260 ms 39708 KB Output is correct
5 Correct 173 ms 31936 KB Output is correct
6 Correct 268 ms 38336 KB Output is correct
7 Correct 181 ms 32000 KB Output is correct
8 Correct 275 ms 40036 KB Output is correct
9 Correct 259 ms 39872 KB Output is correct
10 Correct 187 ms 33096 KB Output is correct
11 Correct 262 ms 39872 KB Output is correct
12 Correct 180 ms 32476 KB Output is correct
13 Correct 273 ms 39872 KB Output is correct
14 Correct 178 ms 32448 KB Output is correct
15 Correct 189 ms 32448 KB Output is correct
16 Correct 173 ms 30656 KB Output is correct
17 Correct 174 ms 31784 KB Output is correct
18 Correct 561 ms 38080 KB Output is correct
19 Correct 285 ms 34500 KB Output is correct
20 Correct 185 ms 34760 KB Output is correct
21 Correct 338 ms 41712 KB Output is correct
22 Correct 240 ms 32960 KB Output is correct
23 Correct 327 ms 40280 KB Output is correct
24 Correct 452 ms 35608 KB Output is correct
25 Correct 305 ms 41984 KB Output is correct
26 Correct 526 ms 41968 KB Output is correct
27 Correct 308 ms 35016 KB Output is correct
28 Correct 387 ms 41416 KB Output is correct
29 Correct 304 ms 34344 KB Output is correct
30 Correct 347 ms 41716 KB Output is correct
31 Correct 275 ms 34424 KB Output is correct
32 Correct 174 ms 34272 KB Output is correct
33 Correct 576 ms 35280 KB Output is correct
34 Correct 242 ms 33780 KB Output is correct