oj.uz

Submission #619690

# Submission time Handle Problem Language Result Execution time Memory
619690 2022-08-02T14:36:03 Z Koosha_mv Distributing Candies (IOI21_candies) C++17
100 / 100
 837 ms 46908 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=2e5+99;
const ll inf=1e16;

int n,q,c[N],a[N];
ll Min[N<<2],Max[N<<2],lz[N<<2];
ll b[N];
vector<int> s,t,val,ad[N],dl[N];

void upd(int id){
    Min[id]=min(Min[id<<1],Min[id<<1|1]);
    Max[id]=max(Max[id<<1],Max[id<<1|1]);
}
void shift(int id){
    lz[id<<1]+=lz[id];
    Min[id<<1]+=lz[id];
    Max[id<<1]+=lz[id];

    lz[id<<1|1]+=lz[id];
    Min[id<<1|1]+=lz[id];
    Max[id<<1|1]+=lz[id];

    lz[id]=0;
}

void add(int L,int R,ll val,int id=1,int l=0,int r=q+1){
    if(r<=L || R<=l) return ;
    if(L<=l && r<=R){
        lz[id]+=val;
        Min[id]+=val;
        Max[id]+=val;
        return ;
    }
    int mid=(l+r)>>1;
    shift(id);
    add(L,R,val,id<<1,l,mid);
    add(L,R,val,id<<1|1,mid,r);
    upd(id);
}
int find(ll d,ll mn=inf,ll mx=-inf,int id=1,int l=0,int r=q+1){
    if(Max[1]-Min[1]<d) return 0;
    if(l+1==r){
        return r;
    }
    int mid=(l+r)>>1;
    shift(id);
    if(max(mx,Max[id<<1|1])-min(mn,Min[id<<1|1])<d){
        return find(d,min(mn,Min[id<<1|1]),max(mx,Max[id<<1|1]),id<<1,l,mid);
    }
    else{
        return find(d,mn,mx,id<<1|1,mid,r);
    }
}
ll get0(int L,int R,int id=1,int l=0,int r=q+1){
    if(r<=L || R<=l) return inf;
    if(L<=l && r<=R){
        return Min[id];
    }
    int mid=(l+r)>>1;
    shift(id);
    return min(get0(L,R,id<<1,l,mid),get0(L,R,id<<1|1,mid,r));
}
ll get1(int L,int R,int id=1,int l=0,int r=q+1){
    if(r<=L || R<=l) return -inf;
    if(L<=l && r<=R){
        return Max[id];
    }
    int mid=(l+r)>>1;
    shift(id);
    return max(get1(L,R,id<<1,l,mid),get1(L,R,id<<1|1,mid,r));
}
int find0(ll d,int id=1,int l=0,int r=q+1){
    if(d<=Min[1]) return 0;
    if(l+1==r){
        return r;
    }
    int mid=(l+r)>>1;
    shift(id);
    if(Min[id<<1|1]>=d){
        return find0(d,id<<1,l,mid);
    }
    else{
        return find0(d,id<<1|1,mid,r);
    }
}
int find1(ll d,int id=1,int l=0,int r=q+1){
    if(d>=Max[1]) return 0;
    if(l+1==r){
        return r;
    }
    int mid=(l+r)>>1;
    shift(id);
    if(Max[id<<1|1]<=d){
        return find1(d,id<<1,l,mid);
    }
    else{
        return find1(d,id<<1|1,mid,r);
    }
}

vector<int> distribute_candies(vector<int> _c,vector<int> _s,vector<int> _t,vector<int> _val){
    s=_s,t=_t,val=_val;
    n=_c.size(),q=s.size();
    vector<int> ans(n);
    f(i,0,n) c[i]=_c[i];
    f(i,0,q){
        ad[s[i]].pb(i);
        dl[t[i]].pb(i);
    }
    f(i,0,n){
        for(auto x : ad[i]) a[x+1]+=val[x];
        for(auto x : ad[i]) add(x+1,q+1,val[x]);
        //dbga(b,0,q+1);
        int p=find(c[i]);
        int b0=find0(get0(p,q+1));
        int b1=find1(get1(p,q+1));
        //cout<<p<<" - "<<b0<<" "<<b1<<endl;
        ll mn=get0(p,q+1);
        ll mx=get1(p,q+1);

        ans[i]=get0(q,q+1)-get0(p,q+1);
        if(b1<b0){
            ans[i]=c[i]-(get1(p,q+1)-get1(q,q+1));
        }

        for(auto x : dl[i]) add(x+1,q+1,-val[x]);
        for(auto x : dl[i]) a[x+1]-=val[x];
    }
    return ans;
}
/*
3
10 15 13
2
0 2 20
0 1 -11

*/

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:140:12: warning: unused variable 'mn' [-Wunused-variable]
  140 |         ll mn=get0(p,q+1);
      |            ^~
candies.cpp:141:12: warning: unused variable 'mx' [-Wunused-variable]
  141 |         ll mx=get1(p,q+1);
      |            ^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 7 ms 9940 KB Output is correct
5 Correct 9 ms 9940 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 40216 KB Output is correct
2 Correct 681 ms 44280 KB Output is correct
3 Correct 617 ms 44120 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 205 ms 32772 KB Output is correct
3 Correct 204 ms 14236 KB Output is correct
4 Correct 670 ms 40140 KB Output is correct
5 Correct 711 ms 46516 KB Output is correct
6 Correct 681 ms 46908 KB Output is correct
7 Correct 608 ms 46244 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9636 KB Output is correct
2 Correct 5 ms 9756 KB Output is correct
3 Correct 141 ms 31644 KB Output is correct
4 Correct 226 ms 13180 KB Output is correct
5 Correct 434 ms 34792 KB Output is correct
6 Correct 587 ms 35072 KB Output is correct
7 Correct 607 ms 35112 KB Output is correct
8 Correct 502 ms 35060 KB Output is correct
9 Correct 544 ms 35092 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 7 ms 9940 KB Output is correct
5 Correct 9 ms 9940 KB Output is correct
6 Correct 707 ms 40216 KB Output is correct
7 Correct 681 ms 44280 KB Output is correct
8 Correct 617 ms 44120 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 205 ms 32772 KB Output is correct
11 Correct 204 ms 14236 KB Output is correct
12 Correct 670 ms 40140 KB Output is correct
13 Correct 711 ms 46516 KB Output is correct
14 Correct 681 ms 46908 KB Output is correct
15 Correct 608 ms 46244 KB Output is correct
16 Correct 5 ms 9636 KB Output is correct
17 Correct 5 ms 9756 KB Output is correct
18 Correct 141 ms 31644 KB Output is correct
19 Correct 226 ms 13180 KB Output is correct
20 Correct 434 ms 34792 KB Output is correct
21 Correct 587 ms 35072 KB Output is correct
22 Correct 607 ms 35112 KB Output is correct
23 Correct 502 ms 35060 KB Output is correct
24 Correct 544 ms 35092 KB Output is correct
25 Correct 6 ms 9684 KB Output is correct
26 Correct 152 ms 14332 KB Output is correct
27 Correct 244 ms 35376 KB Output is correct
28 Correct 662 ms 44752 KB Output is correct
29 Correct 758 ms 45260 KB Output is correct
30 Correct 770 ms 45340 KB Output is correct
31 Correct 826 ms 45532 KB Output is correct
32 Correct 837 ms 45816 KB Output is correct