oj.uz

Submission #1102792

# Submission time Handle Problem Language Result Execution time Memory
1102792 2024-10-18T23:33:18 Z vladilius Measures (CEOI22_measures) C++17
45 / 100
 615 ms 41408 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, 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 4 ms 848 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 3 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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 848 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 3 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 Incorrect 615 ms 38848 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 243 ms 37824 KB Output is correct
2 Correct 176 ms 32740 KB Output is correct
3 Correct 192 ms 34088 KB Output is correct
4 Correct 249 ms 41408 KB Output is correct
5 Correct 181 ms 33124 KB Output is correct
6 Correct 262 ms 38516 KB Output is correct
7 Correct 194 ms 33224 KB Output is correct
8 Correct 273 ms 41152 KB Output is correct
9 Correct 260 ms 39872 KB Output is correct
10 Correct 172 ms 32960 KB Output is correct
11 Correct 258 ms 41232 KB Output is correct
12 Correct 180 ms 33728 KB Output is correct
13 Correct 258 ms 41312 KB Output is correct
14 Correct 186 ms 32636 KB Output is correct
15 Correct 170 ms 34148 KB Output is correct
16 Correct 157 ms 31992 KB Output is correct
17 Correct 174 ms 31936 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 37824 KB Output is correct
2 Correct 176 ms 32740 KB Output is correct
3 Correct 192 ms 34088 KB Output is correct
4 Correct 249 ms 41408 KB Output is correct
5 Correct 181 ms 33124 KB Output is correct
6 Correct 262 ms 38516 KB Output is correct
7 Correct 194 ms 33224 KB Output is correct
8 Correct 273 ms 41152 KB Output is correct
9 Correct 260 ms 39872 KB Output is correct
10 Correct 172 ms 32960 KB Output is correct
11 Correct 258 ms 41232 KB Output is correct
12 Correct 180 ms 33728 KB Output is correct
13 Correct 258 ms 41312 KB Output is correct
14 Correct 186 ms 32636 KB Output is correct
15 Correct 170 ms 34148 KB Output is correct
16 Correct 157 ms 31992 KB Output is correct
17 Correct 174 ms 31936 KB Output is correct
18 Incorrect 521 ms 39076 KB Output isn't correct
19 Halted 0 ms 0 KB -