oj.uz

Submission #705840

# Submission time Handle Problem Language Result Execution time Memory
705840 2023-03-05T13:12:12 Z ToroTN Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 31160 KB 
#include<bits/stdc++.h>
using namespace std;
#include "candies.h"
//#include "grader.cpp"
#define pb push_back
#define X first
#define Y second
#define ll long long
ll mx[800005],mn[800005],lz[800005];
vector<pair<ll,ll> > sweep[200005]; // pair (index of commands, updated value)
vector<int> ans;
void uptlz(ll tree,ll st,ll ed)
{
    mx[tree]+=lz[tree],mn[tree]+=lz[tree];
    if(st!=ed)
    {
        lz[2*tree]+=lz[tree],lz[2*tree+1]+=lz[tree];
    }
    lz[tree]=0;
}
void update(ll tree,ll st,ll ed,ll l,ll r,ll val)
{
    ll md=(st+ed)/2;
    if(st>=l&&ed<=r)
    {
        lz[tree]+=val;
    }
    uptlz(tree,st,ed);
    if(st>r||ed<l)return;
    if(st>=l&&ed<=r)return;
    update(2*tree,st,md,l,r,val);
    update(2*tree+1,md+1,ed,l,r,val);
    mx[tree]=max(mx[2*tree],mx[2*tree+1]);
    mn[tree]=min(mn[2*tree],mn[2*tree+1]);
}
pair<ll,ll> query(ll tree,ll st,ll ed,ll l,ll r)
{
    ll md=(st+ed)/2;
    uptlz(tree,st,ed);
    if(st>r||ed<l)return {-1e18,1e18};
    if(st>=l&&ed<=r)return {mx[tree],mn[tree]};
    return {max(query(2*tree,st,md,l,r).X,query(2*tree+1,md+1,ed,l,r).X),min(query(2*tree,st,md,l,r).Y,query(2*tree+1,md+1,ed,l,r).Y)};
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    ll n = c.size();
    ll m=v.size();
    for(int i=0;i<m;i++)
    {
        sweep[l[i]+1].pb({i+1,v[i]});
        sweep[r[i]+2].pb({i+1,-v[i]});
    }
    /*for(int i=1;i<=n;i++)
    {
        printf("%d\n",i);
        for(int j=0;j<sweep[i].size();j++)
        {
            printf("%d %d\n",sweep[i][j].X,sweep[i][j].Y);
        }
        printf("\n");
    }*/
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<sweep[i].size();j++)
        {
            int cmd=sweep[i][j].X,flag=sweep[i][j].Y;
            update(1,1,m,cmd,m,flag);
        }
        /*printf("i=%d\n",i);
        for(int j=1;j<=m;j++)
        {
            printf("%lld ",query(1,1,m,j,j));
        }
        printf("\n");*/
        ll st=0,md,ed=m;
        while(ed>=st)
        {
            md=(st+ed)/2;
            ll diff;
            pair<ll,ll> rng=query(1,1,m,md,m);
            if(md==0)
            {
                diff=rng.X;
            }else
            {
                diff=rng.X-rng.Y;
            }
            if(diff>c[i-1])
            {
                st=md+1;
            }else
            {
                ed=md-1;
            }
        }
        ll fn=query(1,1,m,m,m).X;//final poll
        ll l1,r1,l2,r2,base;
        if(ed==-1)
        {
            l1=min((ll)0,query(1,1,m,1,m).Y);
            r1=query(1,1,m,1,m).X;
            ans.pb(fn-l1);
        }else 
        {
            if(ed==0)
            {
                l1=0;
                r1=query(1,1,m,1,m).X;
            }else
            {
                l1=query(1,1,m,ed,m).Y;
                r1=query(1,1,m,ed,m).X;
            }
            l2=query(1,1,m,ed+1,m).Y;
            r2=query(1,1,m,ed+1,m).X;
            if(l1==l2)
            {
                base=l1;
            }else
            {
                base=r1-c[i-1];
            }
            ans.pb(fn-base);
        }
    }
    return ans;
}

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:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j=0;j<sweep[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~
candies.cpp:97:21: warning: variable 'r2' set but not used [-Wunused-but-set-variable]
   97 |         ll l1,r1,l2,r2,base;
      |                     ^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 9 ms 5276 KB Output is correct
4 Correct 53 ms 5332 KB Output is correct
5 Correct 981 ms 5372 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5030 ms 27424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Execution timed out 5054 ms 31160 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
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 Execution timed out 5063 ms 28668 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 9 ms 5276 KB Output is correct
4 Correct 53 ms 5332 KB Output is correct
5 Correct 981 ms 5372 KB Output is correct
6 Execution timed out 5030 ms 27424 KB Time limit exceeded
7 Halted 0 ms 0 KB -