oj.uz

Submission #1032686

# Submission time Handle Problem Language Result Execution time Memory
1032686 2024-07-24T06:11:12 Z hotboy2703 Distributing Candies (IOI21_candies) C++17
100 / 100
 333 ms 49428 KB 
#include "candies.h"
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
namespace trung{
    const ll block = 450;
    const ll MAXN = 2e5+100;
    const ll INF = 1e18;
    pll nxt[MAXN][2];
    struct event{
        ll x,i,v;
    };
    ll m,n;
    namespace segtree{
        struct node{
            pll min1,max1;
        };
        const node worst = {MP(INF,-1),MP(-INF,-1)};
        node tree[MAXN*4];
        ll lazy[MAXN*4];
        void push(ll id,ll v){
            lazy[id]+=v;
            tree[id].min1.fi += v;
            tree[id].max1.fi += v;
        }
        void lz(ll id){
            push(id<<1,lazy[id]);
            push(id<<1|1,lazy[id]);
            lazy[id] = 0;
        }
        node combine(node x,node y){
            node res;
            if (y.min1.fi < x.min1.fi)res.min1=y.min1;
            else res.min1 = x.min1;
            if (y.max1.fi > x.max1.fi)res.max1=y.max1;
            else res.max1 = x.max1;
            return res;
        }
        void build(ll id = 1,ll l = 0,ll r = m){
            tree[id] = {MP(0,l),MP(0,l)};
            if (l < r){
                ll mid = (l + r) >> 1;
                build(id<<1,l,mid);
                build(id<<1|1,mid+1,r);
            }
        }
        void update(ll i,ll v,ll id=1,ll l = 0,ll r = m){
            // cout<<id<<' '<<l<<' '<<r<<endl;
            if (r < i)return;
            if (i <= l){
                push(id,v);
                return;
            }
            lz(id);
            ll mid = (l + r) >> 1;
            update(i,v,id<<1,l,mid);
            update(i,v,id<<1|1,mid+1,r);
            tree[id] = combine(tree[id<<1],tree[id<<1|1]);
        }
        node get(ll l1,ll r1,ll id = 1,ll l = 0,ll r = m){
            if (l > r1 || l1 > r)return worst;
            if (l1 <= l && r <= r1){
                return tree[id];
            }
            lz(id);
            ll mid = (l + r) >> 1;
            return combine(get(l1,r1,id<<1,l,mid),get(l1,r1,id<<1|1,mid+1,r));
        }
        node get_last(ll c,node suf = worst,ll id = 1,ll l = 0,ll r = m){
            node sus = combine(suf,tree[id]);
            if (sus.max1.fi - sus.min1.fi <= c)return sus;
            if (l==r){
                return sus;
            }
            lz(id);
            ll mid = (l + r) >> 1;
            node res = get_last(c,suf,id<<1|1,mid+1,r);
            if (res.max1.fi - res.min1.fi <= c)res = get_last(c,res,id<<1,l,mid);
            return res;
        }
    }
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    using namespace trung;
    n = c.size();
    m = sz(l);
    vector <event> all;
    for (ll i = 0;i < m;i ++){
        all.push_back({l[i],i+1,v[i]});
        all.push_back({r[i]+1,i+1,-v[i]});
    }
    sort(all.begin(),all.end(),[](event a1,event a2){return a1.x < a2.x;});
    using namespace segtree;
    build();
    vector <int> res(n);
    for (ll i = 0,ptr = 0;i < n;i ++){
        while (ptr < sz(all) && all[ptr].x == i){
            update(all[ptr].i,all[ptr].v);
            ptr++;
        }
        node tmp = get_last(c[i]);
        // cout<<tmp.max1.fi<<' '<<tmp.max1.se<<' '<<tmp.min1.fi<<' '<<tmp.min1.se<<' '<<get(m,m).max1.fi<<endl;
        if (tmp.max1.fi - tmp.min1.fi <= c[i]){
            res[i] = get(m,m).max1.fi - tmp.min1.fi;
        }
        else if (tmp.min1.se > tmp.max1.se){
            res[i] = get(m,m).max1.fi - tmp.min1.fi;
        }
        else{
            res[i] = get(m,m).max1.fi - tmp.max1.fi + c[i];
        }
    }
    return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 3 ms 6912 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 42936 KB Output is correct
2 Correct 270 ms 41644 KB Output is correct
3 Correct 260 ms 41648 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 172 ms 43260 KB Output is correct
3 Correct 72 ms 12292 KB Output is correct
4 Correct 333 ms 48396 KB Output is correct
5 Correct 329 ms 48560 KB Output is correct
6 Correct 297 ms 49428 KB Output is correct
7 Correct 255 ms 48312 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 103 ms 40020 KB Output is correct
4 Correct 62 ms 10440 KB Output is correct
5 Correct 177 ms 45208 KB Output is correct
6 Correct 182 ms 46768 KB Output is correct
7 Correct 189 ms 47536 KB Output is correct
8 Correct 174 ms 45484 KB Output is correct
9 Correct 187 ms 47792 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 3 ms 6912 KB Output is correct
6 Correct 279 ms 42936 KB Output is correct
7 Correct 270 ms 41644 KB Output is correct
8 Correct 260 ms 41648 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 172 ms 43260 KB Output is correct
11 Correct 72 ms 12292 KB Output is correct
12 Correct 333 ms 48396 KB Output is correct
13 Correct 329 ms 48560 KB Output is correct
14 Correct 297 ms 49428 KB Output is correct
15 Correct 255 ms 48312 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 103 ms 40020 KB Output is correct
19 Correct 62 ms 10440 KB Output is correct
20 Correct 177 ms 45208 KB Output is correct
21 Correct 182 ms 46768 KB Output is correct
22 Correct 189 ms 47536 KB Output is correct
23 Correct 174 ms 45484 KB Output is correct
24 Correct 187 ms 47792 KB Output is correct
25 Correct 1 ms 4444 KB Output is correct
26 Correct 59 ms 10420 KB Output is correct
27 Correct 181 ms 41660 KB Output is correct
28 Correct 275 ms 46444 KB Output is correct
29 Correct 294 ms 47560 KB Output is correct
30 Correct 304 ms 46776 KB Output is correct
31 Correct 285 ms 48312 KB Output is correct
32 Correct 297 ms 48408 KB Output is correct