oj.uz

Submission #849068

# Submission time Handle Problem Language Result Execution time Memory
849068 2023-09-14T04:12:12 Z 12345678 Distributing Candies (IOI21_candies) C++17
0 / 100
 335 ms 55376 KB 
#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

ll sm;
vector<vector<pair<int, int>>> d(nx);

struct node
{
    ll mx, mn, mxidx, mnidx, lz;
    node(int idx): mx(0), mn(0), mxidx(idx), mnidx(idx), lz(0){}
    node(): lz(0){}
};

struct segtree
{
    node d[4*nx];
    node merge(node &a, node &b)
    {
        node res=node(0);
        res.mx=max(a.mx, b.mx);
        res.mn=min(a.mn, b.mn);
        res.mxidx=a.mx>=b.mx?a.mxidx:b.mxidx;
        res.mnidx=a.mn<=b.mn?a.mnidx:b.mnidx;
        res.lz=0;
        return res;
    }
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i]=node(l));
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    void pushlz(int l, int r, int i)
    {
        d[i].mx+=d[i].lz; d[i].mn+=d[i].lz;
        if (l==r) return void(d[i].lz=0);
        d[2*i].lz+=d[i].lz;
        d[2*i+1].lz+=d[i].lz;
        d[i].lz=0;
    }
    void update(int l, int r, int i, int ql, int v)
    {
        pushlz(l, r, i);
        if (r<ql) return;
        if (ql<=l) return d[i].lz+=v, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, v);
        update(md+1, r, 2*i+1, ql, v);
        d[i]=merge(d[2*i], d[2*i+1]);
    }
    node query(int l, int r, int i, ll c, node ans)
    {
        pushlz(l, r, i);
        if (l==r) return merge(d[i], ans);
        int md=(l+r)/2;
        pushlz(l, md, 2*i); pushlz(md+1, r, 2*i+1);
        node tmp=merge(ans, d[2*i+1]);
        if (tmp.mx-tmp.mn>=c) return query(md+1, r, 2*i+1, c, ans);
        return query(l, md, 2*i, c, tmp); 
    }
} s;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n=c.size(), t=l.size();
    d[0].push_back({1, 1e9+5});
    d[0].push_back({2, -1e9-5});
    for (int i=1; i<=t; i++)
    {
        d[l[i-1]].push_back({i+2, v[i-1]});
        d[r[i-1]+1].push_back({i+2, -v[i-1]});
    }
    vector<int> ans(n);
    for (int i=0; i<n; i++)
    {
        for (auto [x, y]:d[i]) sm+=y, s.update(1, t+2, 1, x, y);
        node tmp(-1);
        tmp.mx=LLONG_MIN; tmp.mn=LLONG_MAX;
        node res=s.query(1, t+2, 1, c[i], tmp);
        //cout<<t+2<<' '<<i<<' '<<c[i]<<' '<<res.mx<<' '<<res.mn<<' '<<res.mxidx<<' '<<res.mnidx<<'\n';
        if (res.mnidx<=res.mxidx) ans[i]=max(0ll, c[i]-(res.mx-sm));
        else ans[i]=max(0ll, sm-res.mn);
    }
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 335 ms 55376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 36444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 36444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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