oj.uz

Submission #939508

# Submission time Handle Problem Language Result Execution time Memory
939508 2024-03-06T12:34:48 Z haxorman Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 50552 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define ll long long

const int mxN = 2e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));

int n, q;
ll lazy[4*mxN];
pair<ll,int> seg[4*mxN][2];
vector<pair<int,int>> que[mxN][2];

void push(int ind, int l, int r, int cnt = 1) {
    seg[ind][0].f += lazy[ind];
    seg[ind][1].f += lazy[ind];

    if (l != r) {
        lazy[2*ind] += lazy[ind];
        lazy[2*ind+1] += lazy[ind];

        if (cnt) {
            int mid = (l+r)/2;
            push(2*ind,l,mid,cnt-1);
            push(2*ind+1,mid+1,r,cnt-1);
        }
    }
    lazy[ind] = 0;
}

void update(int lo, int hi, int inc, int ind = 1, int l = 0, int r = SZ - 1) {
    push(ind,l,r);
    if (lo > r || l > hi) {
        return;
    }

    if (lo <= l && r <= hi) {
        lazy[ind] += inc;
        push(ind,l,r);
        return;
    }
    
    int mid = (l+r)/2;
    update(lo,hi,inc,2*ind,l,mid);
    update(lo,hi,inc,2*ind+1,mid+1,r);
    
    if (seg[2*ind][0].f < seg[2*ind+1][0].f) seg[ind][0] = seg[2*ind][0];
    else seg[ind][0] = seg[2*ind+1][0];

    if (seg[2*ind][1].f > seg[2*ind+1][1].f) seg[ind][1] = seg[2*ind][1];
    else seg[ind][1] = seg[2*ind+1][1];
}

// {min, max}
pair<pair<ll,int>,pair<ll,int>>
query(int lo, int hi, int ind = 1, int l = 0, int r = SZ - 1) {
    push(ind,l,r);
    if (lo > r || l > hi) {
        return {{LLONG_MAX,0}, {LLONG_MIN,0}};
    }

    if (lo <= l && r <= hi) {
        return {seg[ind][0], seg[ind][1]};
    }

    int mid = (l+r)/2;
    auto a = query(lo,hi,2*ind,l,mid), b = query(lo,hi,2*ind+1,mid+1,r);
    auto res = make_pair(min(a.f,b.f), max(a.s,b.s));
    return res;
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    n = c.size(), q = v.size()+1;

    seg[1+SZ][0] = seg[1+SZ][1] = {0, 1};
    for (int i = 2; i <= q; ++i) {
        que[l[i-2]][0].push_back({v[i-2], i});
        que[r[i-2]][1].push_back({v[i-2], i});

        seg[i+SZ][0] = seg[i+SZ][1] = {0, i};
    }
    
    for (int ind = SZ-1; ind >= 0; --ind) {
        if (seg[2*ind][0].f < seg[2*ind+1][0].f) seg[ind][0] = seg[2*ind][0];
        else seg[ind][0] = seg[2*ind+1][0];

        if (seg[2*ind][1].f > seg[2*ind+1][1].f) seg[ind][1] = seg[2*ind][1];
        else seg[ind][1] = seg[2*ind+1][1];
    }
    
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        for (auto [val, t] : que[i][0]) {
            update(t, q, val);
        }
        update(1,q,-c[i]);
        
        /*
        for (int j = 0; j <= q; ++j) {
            cout << query(j,j).f.f << ' ';
        }
        cout << "\n";
        */
    
        int lb = 0, rb = n - 1;
        ll res = query(q,q).f.f;
        while (lb <= rb) {
            int mb = (lb+rb)/2;
            auto cur = query(mb,q);

            if (cur.s.f - cur.f.f >= (ll) c[i]) {
                lb = mb + 1;

                if (cur.s.s > cur.f.s) {
                    res = c[i] + query(q,q).f.f - query(cur.s.s,cur.s.s).f.f;
                }
                else {
                    res = query(q,q).f.f - query(cur.f.s,cur.f.s).f.f;
                }
            }
            else {
                rb = mb - 1;
            }
        }
        ans[i] = res;
        
        update(1,q,c[i]);
        for (auto [val, t] : que[i][1]) {
            update(t, q, -val);
        }
    }
    return ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21080 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Incorrect 9 ms 21084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5006 ms 49768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21080 KB Output is correct
2 Correct 670 ms 43188 KB Output is correct
3 Correct 3107 ms 26920 KB Output is correct
4 Execution timed out 5072 ms 50552 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21084 KB Output is correct
2 Incorrect 14 ms 21084 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21080 KB Output is correct
2 Correct 4 ms 21080 KB Output is correct
3 Incorrect 9 ms 21084 KB Output isn't correct
4 Halted 0 ms 0 KB -