oj.uz

Submission #811190

# Submission time Handle Problem Language Result Execution time Memory
811190 2023-08-07T02:08:58 Z penguinman Distributing Candies (IOI21_candies) C++17
40 / 100
 5000 ms 50664 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 l = a+N, r = b+N-1;
        while(l < r){
            if(l & 1){
                eval(l);
                if(val > 0) lmax[l] = val;
                else lmin[l] = val;
                lsum[l] += val;
                l++;
            }
            l >>= 1;
            if((r&1) == 0){
                eval(r);
                if(val > 0) lmax[r] = val;
                else lmin[r] = val;
                lsum[r] += val;
            }
            r >>= 1;
        }
        if(l){
            eval(l);
            if(val > 0) lmax[l] = val;
            else lmin[l] = val;
            lsum[l] += val;
        }
    }*/
    void update(ll a, ll b, ll val, ll now = 1, ll l = 0, ll r = -1){
        if(r == -1) r = N;
        if(r <= a || b <= l) return;
        eval(now);
        if(a <= l && r <= b){
            if(val > 0) lmax[now] = val;
            else lmin[now] = val;
            lsum[now] += val;
            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){
        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);
    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 3 ms 340 KB Output is correct
4 Correct 7 ms 340 KB Output is correct
5 Correct 14 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4244 ms 49896 KB Output is correct
2 Correct 4613 ms 50572 KB Output is correct
3 Correct 4589 ms 50664 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1746 ms 14684 KB Output is correct
3 Correct 470 ms 34908 KB Output is correct
4 Execution timed out 5086 ms 44404 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 391 ms 14604 KB Output is correct
4 Correct 447 ms 35404 KB Output is correct
5 Correct 1352 ms 49360 KB Output is correct
6 Correct 1323 ms 49204 KB Output is correct
7 Correct 1227 ms 48784 KB Output is correct
8 Correct 1359 ms 49436 KB Output is correct
9 Correct 1196 ms 48196 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 340 KB Output is correct
5 Correct 14 ms 724 KB Output is correct
6 Correct 4244 ms 49896 KB Output is correct
7 Correct 4613 ms 50572 KB Output is correct
8 Correct 4589 ms 50664 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1746 ms 14684 KB Output is correct
11 Correct 470 ms 34908 KB Output is correct
12 Execution timed out 5086 ms 44404 KB Time limit exceeded
13 Halted 0 ms 0 KB -