oj.uz

Submission #438749

# Submission time Handle Problem Language Result Execution time Memory
438749 2021-06-28T14:38:00 Z fcmalkcin Distributing Candies (IOI21_candies) C++17
0 / 100
 160 ms 43120 KB 
#include  "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn=1e5+10;
const ll mod =998244353 ;
const ll base=3e18;
struct tk
{
    ll pmn=0,pmx=0, sum=0;
    int chk=-1;
};
tk mer(tk a, tk b)
{
    if (a.chk==-1) return b;
    if (b.chk==-1 ) return a;
    tk c;
    c.sum=a.sum+b.sum;
    c.pmn=min(a.pmn,a.sum+b.pmn);
    c.pmx=max(a.pmx,a.sum+b.pmx);
    c.chk=a.chk;
    return c;
}
tk st[4*maxn];
void update(ll id,ll left,ll right,ll x,ll diff)
{
    if (x>right||x<left) return ;
    if (left==right)
    {

        st[id].sum+=diff;
        st[id].pmn=min(0ll,st[id].sum);
        st[id].pmx=max(0ll,st[id].sum);
        st[id].chk=(st[id].sum>=0);
        return ;
    }
    ll mid=(left+right)/2;
    update(id*2,left,mid,x,diff);
    update(id*2+1,mid+1,right,x,diff);
    st[id]=mer(st[id*2],st[id*2+1]);
}
tk get(ll id,ll left,ll right,ll x,ll y)
{
    tk a;
    if (x>right||y<left||x>y) return a;
    if (x<=left&&y>=right) return st[id];
    ll mid=(left+right)/2;
    return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
}
vector<int> adj[maxn];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    ll n=c.size();
    ll q=l.size();
    update(1,1,q+2,1,-base);
    update(1,1,q+2,2,base);
    for (int i=0;i<q;i++)
    {
        adj[l[i]].pb(i+3);
     if(r[i]+1<n)   adj[r[i]+1].pb(-(i+3));
    }

    vector<int> ans;
    for (int i=0;i<n;i++)
    {
        for (auto to:adj[i])
        {
            if (to>0)
            {
                update(1,1,q+2,to,v[to-3]);
            }
            else
            {
                update(1,1,q+2,-to,-v[-to-3]);
            }
        }
        adj[i].clear();
        ll l=1,h=q+2;
        while (l<=h)
        {
            ll mid=(l+h)/2;
            tk p=get(1,1,q+2,mid,q+2);
            if (p.pmx-p.pmn>=c[i]) l=mid+1;
            else h=mid-1;
        }
        tk nw=get(1,1,q+2,h,q+2);
        /*if (i==n-1)
        {
            cout <<h<<" "<<q+2<<endl;
            cout <<nw.sum<<" "<<nw.pmn<<" "<<nw.pmx<<endl;
        }*/
        //assert(nw.pmx-nw.pmn>=c[i]);
       if (h>2) ans.pb((nw.chk ?(int )(c[i]-(nw.pmx-nw.sum)):(int)(nw.sum-nw.pmn)));
       else
       {
           ans.pb(max(0,(int)(nw.sum-base)));
       }
    }
    return ans;
}


/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    vector<int > l;
    vector<int > r;
    vector<int > v;
    vector<int > t;
    ll n;
     cin>> n;
     while (n--)
     {
         int x;
         cin>> x;
         t.pb(x);
     }
    ll q;
     cin>> q;
     while (q--)
     {
         int a, b, c;
         cin>>a>> b>> c;
         l.pb(a);
         r.pb(b);
         v.pb(c);
     }
     vector<int> ans=distribute_candies(t,l,r,v);
     for (auto to:ans) cout <<to<<endl;


}*/

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 157 ms 35520 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Runtime error 160 ms 43120 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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