oj.uz

Submission #811182

# Submission time Handle Problem Language Result Execution time Memory
811182 2023-08-07T02:01:14 Z penguinman Distributing Candies (IOI21_candies) C++17
32 / 100
 5000 ms 48156 KB 
#include "candies.h"

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
using std::endl;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

struct lazy_segment_tree{
    ll N;
    ll log;
    vi sum, max, min;
    vi lsum, lmax, lmin;
    lazy_segment_tree(ll n){
        N = 1;
        log = 0;
        while(N <= n){
            N *= 2;
            log++;
        }
        sum.resize(2*N);
        max.resize(2*N);
        min.resize(2*N);
        lsum.resize(2*N);
        lmax.resize(2*N);
        lmin.resize(2*N);
    }
    void update(ll a, ll b, ll val, ll now = 1, ll l = 0, ll r = -1){
        if(r == -1) r = N;
        eval(now);
        if(a <= l && r <= b){
            if(val > 0) lmax[now] = val;
            else lmin[now] = val;
            lsum[now] += val;
            return;
        }
        if(r <= a || b <= l) return;
        update(a,b,val,now*2,l,(l+r)/2);
        update(a,b,val,now*2+1,(l+r)/2,r);
    }
    pii calc(ll now){
        now += N;
        per(i,log+1,0){
            eval((now>>i));
        }
        return mp(max[now], min[now]);
    }
    void reset(){
        rep(i,0,2*N){
            max[i] = min[i] = sum[i] = lmax[i] = lmin[i] = lsum[i] = 0;
        }
    }
    void eval(ll now){
        if(lmax[now]){
            max[now] = std::max(max[now], sum[now]+lmax[now]);
            if(now < N){
                lmax[now*2] = std::max(lmax[now*2], lsum[now*2]+lmax[now]);
                lmax[now*2+1] = std::max(lmax[now*2+1], lsum[now*2+1]+lmax[now]);
            }
            lmax[now] = 0;
        }
        if(lmin[now]){
            min[now] = std::min(min[now], sum[now]+lmin[now]);
            if(now < N){
                lmin[now*2] = std::min(lmin[now*2], lsum[now*2]+lmin[now]);
                lmin[now*2+1] = std::min(lmin[now*2+1], lsum[now*2+1]+lmin[now]);
            }
            lmin[now] = 0;
        }
        if(lsum[now]){
            sum[now] += lsum[now];
            if(now < N){
                lsum[now*2] += lsum[now];
                lsum[now*2+1] += lsum[now];
            }
            lsum[now] = 0;
        }
        lmax[now] = lmin[now] = lsum[now] = 0;
    }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int N = c.size();
    ll Q = l.size();
    vi left(N,-1), right(N,Q);
    lazy_segment_tree seg(N);
    while(true){
        seg.reset();
        vi mid(N);
        bool flg = true;
        vii query(Q+1);
        rep(i,0,N){
            if(left[i]+1 < right[i]){
                mid[i] = (left[i]+right[i])/2;
                query[mid[i]].pb(i);
                flg = false;
            }
        }
        if(flg) break;
        per(i,Q,0){
            if(i < Q){
                seg.update(l[i], r[i]+1, v[i]);
            }
            for(auto el: query[i]){
                auto ret = seg.calc(el);
                if(c[el] <= ret.first-ret.second) left[el] = mid[el];
                else right[el] = mid[el];
            }
        }
    }
    vector<int> ans(N);
    {
        vii max(Q+1), min(Q+1);
        rep(i,0,N){
            if(left[i] == -1) max[0].pb(i);
            else{
                if(v[left[i]] > 0){
                    min[left[i]].pb(i);
                }
                else{
                    max[left[i]].pb(i);
                }
            }
        }
        seg.reset();
        per(i,Q,0){
            if(i < Q){
                seg.update(l[i], r[i]+1, v[i]);
            }
            for(auto el: max[i]){
                ans[el] = seg.calc(el).first;
            }
            for(auto el: min[i]){
                ans[el] = c[el]+seg.calc(el).second;
            }
        }
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 7 ms 472 KB Output is correct
5 Correct 16 ms 684 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4970 ms 46872 KB Output is correct
2 Execution timed out 5068 ms 47248 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1951 ms 14592 KB Output is correct
3 Correct 358 ms 34932 KB Output is correct
4 Execution timed out 5074 ms 44344 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 400 ms 14676 KB Output is correct
4 Correct 420 ms 34492 KB Output is correct
5 Correct 1334 ms 46880 KB Output is correct
6 Correct 1285 ms 46800 KB Output is correct
7 Correct 1135 ms 48156 KB Output is correct
8 Correct 1339 ms 47472 KB Output is correct
9 Correct 1008 ms 48156 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 7 ms 472 KB Output is correct
5 Correct 16 ms 684 KB Output is correct
6 Correct 4970 ms 46872 KB Output is correct
7 Execution timed out 5068 ms 47248 KB Time limit exceeded
8 Halted 0 ms 0 KB -