oj.uz

Submission #811171

# Submission time Handle Problem Language Result Execution time Memory
811171 2023-08-07T01:43:20 Z penguinman Distributing Candies (IOI21_candies) C++17
32 / 100
 5000 ms 50180 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){
            lmax[now] = std::max(lmax[now], lsum[now]+val);
            lmin[now] = std::min(lmin[now], lsum[now]+val);
            lsum[now] += val;
            eval(now);
            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 eval(ll now){
        max[now] = std::max(max[now], sum[now]+lmax[now]);
        min[now] = std::min(min[now], sum[now]+lmin[now]);
        sum[now] += lsum[now];
        if(now < N){
            lmax[now*2] = std::max(lmax[now*2], lsum[now*2]+lmax[now]);
            lmin[now*2] = std::min(lmin[now*2], lsum[now*2]+lmin[now]);
            lsum[now*2] += lsum[now];
            lmax[now*2+1] = std::max(lmax[now*2+1], lsum[now*2+1]+lmax[now]);
            lmin[now*2+1] = std::min(lmin[now*2+1], lsum[now*2+1]+lmin[now]);
            lsum[now*2+1] += lsum[now];
        }
        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);
    while(true){
        lazy_segment_tree seg(N);
        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);
                }
            }
        }
        lazy_segment_tree seg(N);
        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 4 ms 340 KB Output is correct
4 Correct 7 ms 468 KB Output is correct
5 Correct 15 ms 720 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5085 ms 44264 KB Time limit exceeded
2 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 1846 ms 17604 KB Output is correct
3 Correct 635 ms 37196 KB Output is correct
4 Execution timed out 5076 ms 50180 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 760 ms 14612 KB Output is correct
4 Correct 602 ms 35376 KB Output is correct
5 Correct 2108 ms 49440 KB Output is correct
6 Correct 2083 ms 49320 KB Output is correct
7 Correct 2044 ms 48792 KB Output is correct
8 Correct 2181 ms 49324 KB Output is correct
9 Correct 2072 ms 48160 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 4 ms 340 KB Output is correct
4 Correct 7 ms 468 KB Output is correct
5 Correct 15 ms 720 KB Output is correct
6 Execution timed out 5085 ms 44264 KB Time limit exceeded
7 Halted 0 ms 0 KB -