oj.uz

Submission #819861

# Submission time Handle Problem Language Result Execution time Memory
819861 2023-08-10T14:30:36 Z TB_ Measures (CEOI22_measures) C++17
100 / 100
 439 ms 43132 KB 
#include <bits/stdc++.h>
using namespace std;
 
// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")
 
// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD
 
// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(ll i=0;i<((ll)n);i++)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;
 
struct Node{
    Node *lnode, *rnode;
    ll l, r, mval = -1e18, lval = 1e18, toAdd = 0;
    ll frontVal = 0;
    Node(int l, int r) : l(l), r(r){
        if(r-l > 1){
            int mid = (l+r) / 2;
            lnode = new Node(l, mid);
            rnode = new Node(mid, r);
            mval = max(lnode->mval, rnode->mval);
            lval = min(lnode->lval, rnode->lval);
        }
    }

    pl query(int lo, int hi){ // max, min
        if(r <= lo || hi <= l) return {-1e18, 1e18};
        if(r <= hi && lo <= l) return {mval, lval};
        push();
        pl res1 = lnode->query(lo, hi);
        pl res2 = rnode->query(lo, hi);
        return {max(res1.F, res2.F), min(res1.S, res2.S)};
    }

    ll queryAmountInfront(int lo, int hi){
        if(r <= lo || hi <= l) return 0;
        if(r <= hi && lo <= l && hi != r) return frontVal;
        if(r-l == 1) {
            frontVal = 1;
            return 0;
        }
        ll res = lnode->queryAmountInfront(lo, hi)+rnode->queryAmountInfront(lo, hi);
        frontVal = lnode->frontVal+rnode->frontVal;
        return res;
    }

    void update(int lo, int hi, ll vals){
        if(r <= lo || hi <= l) return;
        if(r-l == 1){
            mval = max(mval, vals);
            lval = min(lval, vals);
            return;
        }
        push();
        lnode->update(lo, hi, vals);
        rnode->update(lo, hi, vals);
        mval = max(lnode->mval, rnode->mval);
        lval = min(lnode->lval, rnode->lval);
    }

    void add(int lo, int hi, ll val){
        if(r <= lo || hi <= l) return;
        if(r <= hi && lo <= l){
            toAdd+=val;
            mval+=val;
            lval+=val;
            return;
        }
        push();
        lnode->add(lo, hi, val);
        rnode->add(lo, hi, val);
        mval = max(lnode->mval, rnode->mval);
        lval = min(lnode->lval, rnode->lval);
    }

    void push(){
        if(toAdd){
           lnode->mval += toAdd; 
           lnode->lval += toAdd; 
           lnode->toAdd += toAdd;
           rnode->mval += toAdd; 
           rnode->lval += toAdd; 
           rnode->toAdd += toAdd;
           toAdd = 0;
        }
    }
};
 
int main() {
    // cout << fixed << setprecision(20);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);
 
    ll n, m, d, val;
    cin >> n >> m >> d;
    vpl v, order;
    
    fo(i, n){
        cin >> val;
        v.pb({val, 0});
    }
    fo(x, m){
        cin >> val;
        v.pb({val, x+1});
    }
    sort(all(v));
    n = v.size();
    Node st(0, n);

    fo(i, n) order.pb({v[i].S, i});
    sort(all(order));
    ll ans = 0; 

    for(auto &[addIndex, index] : order){
        ll pos = v[index].F;
        st.update(index, index+1, pos-d*st.queryAmountInfront(0, index+1));
        st.add(index+1, n, -d);

        ans = max(ans, st.query(0, index+1).F-st.query(index, n).S);

        if(!addIndex) continue;
        if(ans%2 == 1) cout << fixed << setprecision(1) << ans/2.0 << " ";
        else cout << ans/2 << " ";
    }
 
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 732 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 193 ms 40804 KB Output is correct
10 Correct 202 ms 42768 KB Output is correct
11 Correct 162 ms 42828 KB Output is correct
12 Correct 203 ms 42836 KB Output is correct
13 Correct 159 ms 42300 KB Output is correct
14 Correct 173 ms 42752 KB Output is correct
15 Correct 189 ms 42104 KB Output is correct
16 Correct 163 ms 42828 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 40872 KB Output is correct
2 Correct 252 ms 42960 KB Output is correct
3 Correct 238 ms 42896 KB Output is correct
4 Correct 190 ms 42768 KB Output is correct
5 Correct 217 ms 42852 KB Output is correct
6 Correct 215 ms 42812 KB Output is correct
7 Correct 255 ms 42828 KB Output is correct
8 Correct 222 ms 42816 KB Output is correct
9 Correct 260 ms 42844 KB Output is correct
10 Correct 247 ms 43132 KB Output is correct
11 Correct 265 ms 42744 KB Output is correct
12 Correct 238 ms 42808 KB Output is correct
13 Correct 234 ms 42748 KB Output is correct
14 Correct 205 ms 42768 KB Output is correct
15 Correct 235 ms 42748 KB Output is correct
16 Correct 228 ms 42424 KB Output is correct
17 Correct 209 ms 42764 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 40872 KB Output is correct
2 Correct 252 ms 42960 KB Output is correct
3 Correct 238 ms 42896 KB Output is correct
4 Correct 190 ms 42768 KB Output is correct
5 Correct 217 ms 42852 KB Output is correct
6 Correct 215 ms 42812 KB Output is correct
7 Correct 255 ms 42828 KB Output is correct
8 Correct 222 ms 42816 KB Output is correct
9 Correct 260 ms 42844 KB Output is correct
10 Correct 247 ms 43132 KB Output is correct
11 Correct 265 ms 42744 KB Output is correct
12 Correct 238 ms 42808 KB Output is correct
13 Correct 234 ms 42748 KB Output is correct
14 Correct 205 ms 42768 KB Output is correct
15 Correct 235 ms 42748 KB Output is correct
16 Correct 228 ms 42424 KB Output is correct
17 Correct 209 ms 42764 KB Output is correct
18 Correct 401 ms 42748 KB Output is correct
19 Correct 392 ms 42788 KB Output is correct
20 Correct 250 ms 42808 KB Output is correct
21 Correct 259 ms 42808 KB Output is correct
22 Correct 293 ms 42760 KB Output is correct
23 Correct 220 ms 42816 KB Output is correct
24 Correct 389 ms 42744 KB Output is correct
25 Correct 207 ms 42832 KB Output is correct
26 Correct 399 ms 42956 KB Output is correct
27 Correct 434 ms 43100 KB Output is correct
28 Correct 297 ms 42768 KB Output is correct
29 Correct 372 ms 42768 KB Output is correct
30 Correct 261 ms 42776 KB Output is correct
31 Correct 280 ms 42820 KB Output is correct
32 Correct 260 ms 42832 KB Output is correct
33 Correct 439 ms 42412 KB Output is correct
34 Correct 263 ms 42848 KB Output is correct