oj.uz

Submission #721206

# Submission time Handle Problem Language Result Execution time Memory
721206 2023-04-10T13:49:47 Z n0sk1ll Distributing Candies (IOI21_candies) C++17
100 / 100
 629 ms 36396 KB 
#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

const li inf=1e18;

li mn[550001],mx[550001],upd[550001];
int l[550001],r[550001],k=1;

void Upd(int p)
{
    mn[p]+=upd[p],mx[p]+=upd[p];
    if (p<k) upd[2*p]+=upd[p],upd[2*p+1]+=upd[p];
    upd[p]=0;
}

void Add(int p, int ll, int rr, int x)
{
    if (rr<l[p] || ll>r[p]) Upd(p);
    else if (ll<=l[p] && rr>=r[p]) upd[p]+=x,Upd(p);
    else Upd(p),Add(2*p,ll,rr,x),Add(2*p+1,ll,rr,x),mn[p]=min(mn[2*p],mn[2*p+1]),mx[p]=max(mx[2*p],mx[2*p+1]);
}

vector<int> cvorovi;
void rastavi(int p, int ll, int rr)
{
    if (ll>r[p] || rr<l[p]) return;
    if (ll<=l[p] && rr>=r[p]) Upd(p),cvorovi.pb(p);
    else Upd(p),rastavi(2*p,ll,rr),rastavi(2*p+1,ll,rr);
}

int WalkRaz(int p, int x, li tmn, li tmx)
{
    Upd(p);
    if (max(tmx,mx[p])-min(tmn,mn[p])<x) return -1;
    if (p>=k) return p-k;
    int mozda=WalkRaz(2*p+1,x,tmn,tmx);
    if (mozda==-1) return WalkRaz(2*p,x,min(tmn,mn[2*p+1]),max(tmx,mx[2*p+1]));
    return mozda;
}

int WalkMin(int p)
{
    Upd(p);
    if (p>=k) return p-k;
    Upd(2*p),Upd(2*p+1);
    if (mn[p]==mn[2*p+1]) return WalkMin(2*p+1);
    return WalkMin(2*p);
}

int WalkMax(int p)
{
    Upd(p);
    if (p>=k) return p-k;
    Upd(2*p),Upd(2*p+1);
    if (mx[p]==mx[2*p+1]) return WalkMax(2*p+1);
    return WalkMax(2*p);
}

void ispisi()
{
    ff(i,1,2*k) Upd(i);
    for (int kk=1;kk<=k;kk*=2)
    {
        ff(i,kk,2*kk) cout<<"("<<mn[i]<<","<<mx[i]<<") ";
        cout<<endl;
    } cout<<endl;
}

vector<pair<bool,pii>> qry[200005]; //add (or remove) : time kad dodajemo : sta dodajemo (potenicjalno negativno)

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V)
{
    int n=(int)C.size();
    int q=(int)V.size();

    while (k<q) k*=2;
    ff(i,0,k) l[i+k]=i,r[i+k]=i;
    bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
    ff(i,q,k) mn[i+k]=inf,mx[i+k]=-inf;
    bff(i,1,k) mn[i]=min(mn[2*i],mn[2*i+1]);
    bff(i,1,k) mx[i]=max(mx[2*i],mx[2*i+1]);

    ff(i,0,q)
    {
        qry[L[i]].pb({1,{i,V[i]}});
        qry[R[i]+1].pb({0,{i,V[i]}});
    }

    vector<int> ans(n,0);

    li suma=0;
    ff(i,0,n)
    {
        for (auto it : qry[i])
        {
            bool dodajem=it.xx;
            int kad=it.yy.xx;
            int sta=it.yy.yy;

            if (dodajem) Add(1,kad,q-1,sta),suma+=sta;
            else Add(1,kad,q-1,-sta),suma-=sta;
        }

        Upd(1);

        //ispisi();

        if (mx[1]-mn[1]<=C[i])
        {
            if (mx[1]>C[i]) ans[i]=C[i]-(mx[1]-suma);
            else
            {
                int djemin=WalkMin(1);
                if (mn[djemin+k]<0) ans[i]=suma-mn[djemin+k];
                else ans[i]=suma;
            }
        }
        else
        {
            int dje=WalkRaz(1,C[i],inf,-inf);

            rastavi(1,dje,q-1);
            int mp=cvorovi[0];
            for (auto p : cvorovi) if (mn[p]<mn[mp]) mp=p;
            int djemin=WalkMin(mp);

            mp=cvorovi[0];
            for (auto p : cvorovi) if (mx[p]>mx[mp]) mp=p;
            int djemax=WalkMax(mp);
            cvorovi.clear();

            if (djemin>djemax) ans[i]=min((li)C[i],suma-mn[djemin+k]);
            else ans[i]=max(0ll,C[i]-(mx[djemax+k]-suma));
        }
    }

    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 5 ms 5272 KB Output is correct
4 Correct 5 ms 5332 KB Output is correct
5 Correct 6 ms 5276 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 36132 KB Output is correct
2 Correct 584 ms 36264 KB Output is correct
3 Correct 629 ms 36380 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 320 ms 32256 KB Output is correct
3 Correct 148 ms 9276 KB Output is correct
4 Correct 593 ms 36396 KB Output is correct
5 Correct 620 ms 36264 KB Output is correct
6 Correct 543 ms 36172 KB Output is correct
7 Correct 511 ms 36396 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 142 ms 30360 KB Output is correct
4 Correct 99 ms 8192 KB Output is correct
5 Correct 283 ms 32772 KB Output is correct
6 Correct 267 ms 32624 KB Output is correct
7 Correct 255 ms 32512 KB Output is correct
8 Correct 277 ms 32540 KB Output is correct
9 Correct 362 ms 32700 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 5 ms 5272 KB Output is correct
4 Correct 5 ms 5332 KB Output is correct
5 Correct 6 ms 5276 KB Output is correct
6 Correct 548 ms 36132 KB Output is correct
7 Correct 584 ms 36264 KB Output is correct
8 Correct 629 ms 36380 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 320 ms 32256 KB Output is correct
11 Correct 148 ms 9276 KB Output is correct
12 Correct 593 ms 36396 KB Output is correct
13 Correct 620 ms 36264 KB Output is correct
14 Correct 543 ms 36172 KB Output is correct
15 Correct 511 ms 36396 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 4 ms 4948 KB Output is correct
18 Correct 142 ms 30360 KB Output is correct
19 Correct 99 ms 8192 KB Output is correct
20 Correct 283 ms 32772 KB Output is correct
21 Correct 267 ms 32624 KB Output is correct
22 Correct 255 ms 32512 KB Output is correct
23 Correct 277 ms 32540 KB Output is correct
24 Correct 362 ms 32700 KB Output is correct
25 Correct 3 ms 4948 KB Output is correct
26 Correct 94 ms 8172 KB Output is correct
27 Correct 338 ms 32392 KB Output is correct
28 Correct 579 ms 36324 KB Output is correct
29 Correct 576 ms 36304 KB Output is correct
30 Correct 585 ms 36368 KB Output is correct
31 Correct 555 ms 36168 KB Output is correct
32 Correct 534 ms 36276 KB Output is correct