oj.uz

Submission #1049027

# Submission time Handle Problem Language Result Execution time Memory
1049027 2024-08-08T12:10:57 Z Malix Distributing Candies (IOI21_candies) C++17
11 / 100
 266 ms 9052 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,ll,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

vector<ll> ft;
int n,q;
vi a,st,loc,st2,loc2;
int mx=1e9;

void update(int x,ll y){
    x++;
    while(x<n+1){
        ft[x]+=y;
        x+=LSOne(x);
    }
}

ll solve(int x){
    x++;
    ll ans=0;
    while(x){
        ans+=ft[x];
        x-=LSOne(x);
    }
    return ans;
}

void build(int x,int l,int r){
    if(l==r){
        st[x]=a[l];
        loc[x]=l;
        st2[x]=a[l];
        loc2[x]=-l;
        return;
    }
    int m=(l+r)/2;
    build(2*x,l,m);
    build(2*x+1,m+1,r);
    st[x]=max(st[2*x],st[2*x+1]);
    st2[x]=min(st2[2*x],st2[2*x+1]);
    if(st[2*x]<=st[2*x+1])loc[x]=loc[2*x+1];
    else loc[x]=loc[2*x];
    if(st2[2*x]>=st2[2*x+1])loc2[x]=loc2[2*x+1];
    else loc2[x]=loc2[2*x];
}

pi maximum(int x,int l,int r,int a,int b){
    if(a>b)return {-1,-1};
    if(l==a&&r==b)return {st[x],loc[x]};
    int m=(l+r)/2;
    return max(maximum(2*x,l,m,a,min(b,m)),maximum(2*x+1,m+1,r,max(a,m+1),b));
}

pi minimum(int x,int l,int r,int a,int b){
    if(a>b)return {inf,inf};
    if(l==a&&r==b)return {st2[x],loc2[x]};
    int m=(l+r)/2;
    return min(minimum(2*x,l,m,a,min(b,m)),minimum(2*x+1,m+1,r,max(a,m+1),b));
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n=c.size(),q=l.size();
if(n<=2000){
    vi ans(n,0);
    REP(i,0,q)REP(j,l[i],r[i]+1)ans[j]=max(0,min(c[j],ans[j]+v[i]));
    return ans;
}
    bool flag=1;
    REP(i,0,n)if(v[i]<0)flag=0;
if(flag){
    vi ans(n);
    ft.resize(n+1,0);
    REP(i,0,q){
        update(l[i],(ll)v[i]);
        update(r[i]+1,(ll)(-v[i]));
    }
    REP(i,0,n){
        ll x=solve(i);
        if(x>1e9)x=1e9;
        ans[i]=min(c[i],(int)x);
    }
    return ans;
}
    int pos=0;
    ll tot=0;
    flag=0;
    while(pos<q){
        while(pos<q&&v[pos]>0){
            tot+=v[pos];
            pos++;
        }
        a.PB(tot);
        if(tot>=mx){
            a.clear();
            flag=1;
            tot=mx;
        }
        while(pos<q&&v[pos]<0){
            tot+=v[pos];
            pos++;
        }
        a.PB(tot);
        if(tot<=0){
            a.clear();
            flag=0;
            tot=0;
        }
    }
    int m=a.size();
    if(m==0){
        vi ans(n);
        if(flag)REP(i,0,n)ans[i]=c[i];
        else REP(i,0,n)ans[i]=0;
        return ans;
    }
    st.resize(4*m+1);loc.resize(4*m+1);
    st2.resize(4*m+1);loc2.resize(4*m+1);
    build(1,0,m-1);
    pos=0;int lval=0,rval=1e9;
    vector<tii> arr;
    if(flag){
        pi val=minimum(1,0,m-1,pos,m-1);
        lval=val.F;pos=-val.S+1;
        arr.PB({rval-lval,a[m-1]-(-val.S-1<0?0:a[-val.S-1]),1});
    }
    while(pos<m){
        pi val=maximum(1,0,m-1,pos,m-1);
        rval=val.F;pos=val.S+1;
        arr.PB({rval-lval,a[m-1]-(val.S-1<0?0:a[val.S-1]),0});
        if(pos>=m)break;
        val=minimum(1,0,m-1,pos,m-1);
        lval=val.F;pos=-val.S+1;
        arr.PB({rval-lval,a[m-1]-(-val.S-1<0?0:a[-val.S-1]),1});
    }
    arr.PB({0,0,0});
    reverse(arr.begin(),arr.end());
    vi ans(n);
    REP(i,0,n){
        tuple<int,ll,int> temp={c[i],-1,-1};
        auto it=upper_bound(arr.begin(),arr.end(),temp);
        it--;
        ll x=get<1>(*it);
        int y=get<2>(*it);
        if(y==1)ans[i]=c[i];
        else ans[i]=0;
        ans[i]+=(int)x;
    }
    return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 344 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 9040 KB Output is correct
2 Correct 62 ms 9040 KB Output is correct
3 Correct 65 ms 9052 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 127 ms 5160 KB Output is correct
3 Runtime error 15 ms 3788 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 266 ms 5116 KB Output is correct
4 Runtime error 14 ms 4952 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 64 ms 9040 KB Output is correct
7 Correct 62 ms 9040 KB Output is correct
8 Correct 65 ms 9052 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 127 ms 5160 KB Output is correct
11 Runtime error 15 ms 3788 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -