oj.uz

Submission #853111

# Submission time Handle Problem Language Result Execution time Memory
853111 2023-09-23T12:43:09 Z onepunchac168 Distributing Candies (IOI21_candies) C++17
67 / 100
 1205 ms 44624 KB 
//------------------------------------\\
//   ------------------------------   \\
//  |  created by Dinh Manh Hung   |  \\
//  |      tht.onepunchac168       |  \\
//  |     THPT CHUYEN HA TINH      |  \\
//  |      HA TINH, VIET NAM       |  \\
//  |           Siuuu              |  \\
//   ------------------------------   \\
//------------------------------------\\

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

#define            task     ""
#define       file(name)    if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define             ldb     long double
#define              pb     push_back
#define              eb     emplace_back
#define              fi     first
#define              se     second
#define           all(x)    begin(x),end(x)
#define       uniquev(v)    v.resize(unique(all(v))-v.begin())
#define       rep(i,a,b)    for (int i=a;i<=b;i++)
#define        cntbit(v)    __builtin_popcountll(v)
#define         gcd(a,b)    __gcd(a,b)
#define         lcm(a,b)    ((1LL*a*b)/__gcd(a,b))
#define          mask(x)    (1LL<<(x))
#define     readbit(x,i)    ((x>>i)&1)
#define             Yes     cout << "Yes"
#define             YES     cout << "YES"
#define              No     cout << "No"
#define              NO     cout << "NO"

typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;

ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};

const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const ll mod=1e9+7;
const char nl = '\n';

inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = (xo<<1) + (xo<<3) + co - '0';
    return xo;
}

void WriteInt(int xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}
/*
// DEBUG

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
*/

/* END OF TEMPLATE*/

// ================= Solution =================//

/*
void onepunchac168();

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    file(task);
    int tests;
    tests=1;
    //cin>>tests;
    while (tests--)
    {
        onepunchac168();
    }
}
*/

const int N=2e5+5;
const int Q=2e5+5;

int n,q;
vector <ii> vt[N];
ll maxsuff[4*N];
ll minsuff[4*N];
ll sum[4*N];
ll ss[N];
ll cnt[N];
void update(int node,int l,int r,int u,ll val)
{
    if (l>u||r<u)
    {
        return;
    }
    if (l==r)
    {
        sum[node]=val;
        maxsuff[node]=val;
        minsuff[node]=val;
        return;
    }
    update(node*2,l,(l+r)/2,u,val);
    update(node*2+1,(l+r)/2+1,r,u,val);
    sum[node]=sum[node*2]+sum[node*2+1];
    maxsuff[node]=max(maxsuff[node*2],maxsuff[node*2+1]+sum[node*2]);
    minsuff[node]=min(minsuff[node*2],minsuff[node*2+1]+sum[node*2]);
}
ll querymax(int node,int l,int r,int u,int v,ll val)
{
    if (l>v||r<u)
    {
        return -1e18-5;
    }
    if (l>=u&&r<=v)
    {
        return maxsuff[node]+val;
    }
    ll aa=querymax(node*2,l,(l+r)/2,u,v,val);
    ll bb=querymax(node*2+1,(l+r)/2+1,r,u,v,val+sum[node*2]);
    return max(aa,bb);
}
ll querymin(int node,int l,int r,int u,int v,ll val)
{
    if (l>v||r<u)
    {
        return 1e18+5;
    }
    if (l>=u&&r<=v)
    {
        return minsuff[node]+val;
    }
    ll aa=querymin(node*2,l,(l+r)/2,u,v,val);
    ll bb=querymin(node*2+1,(l+r)/2+1,r,u,v,val+sum[node*2]);
    return min(aa,bb);
}
ll querysum(int node,int l,int r,int u,int v)
{
    if (l>v||r<u)
    {
        return 0;
    }
    if (l>=u&&r<=v)
    {
        return sum[node];
    }
    return querysum(node*2,l,(l+r)/2,u,v)+querysum(node*2+1,(l+r)/2+1,r,u,v);
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,std::vector<int> r, std::vector<int> v) {
    n = c.size();
    vector <int > ans(n);
    q= l.size();
    for (int i=0;i<q;i++)
    {
        vt[l[i]+1].pb({i,1});
        ss[l[i]+1]+=v[i];
        cnt[l[i]+1]++;
        cnt[r[i]+2]--;
        ss[r[i]+2]-=v[i];
        vt[r[i]+2].pb({i,-1});
    }
    ss[0]=0;
    for (int i=1;i<=n;i++)
    {
        ss[i]+=ss[i-1];
        cnt[i]+=cnt[i-1];
        for (auto u:vt[i])
        {
            if (u.se==1)
            {
                update(1,1,q,u.fi+1,v[u.fi]);
                //cout<<u.fi<<" "<<v[u.fi]<<nl;
                continue;
            }
            update(1,1,q,u.fi+1,0);
        }
        if (cnt[i]==0)
        {
            ans[i-1]=0;
            continue;
        }
        int left=1;
        ll res=-1,la=0,ra=0;
        int right=q;
        while (left<=right)
        {
            int mid=(left+right)/2;
            ll aa=querymax(1,1,q,mid,q,0);
            ll bb=querymin(1,1,q,mid,q,0);
            if (aa-bb>c[i-1])
            {
                res=mid;
                la=aa;
                ra=bb;
                left=mid+1;
            }
            else right=mid-1;
        }
        //cout<<querymax(1,1,q,res,q,0)<<" "<<ss[i]<<nl;
        if (res==-1)
        {
            ans[i-1]=ss[i]-min(0LL,querymin(1,1,q,1,q,0));
        }
        else
        {
            res++;
            if (querysum(1,1,q,1,res-1)<ss[i])
            {
                ans[i-1]=c[i-1]-(querymax(1,1,q,res,q,0)-ss[i]);
            }
            else
            {
                ans[i-1]=ss[i]-querymin(1,1,q,res,q,0);
            }
        }

    }
    return ans;
}

/*
void onepunchac168()
{

}
*/

// goodbye see ya

Compilation message

candies.cpp:1:1: warning: multi-line comment [-Wcomment]
    1 | //------------------------------------\\
      | ^
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:223:19: warning: variable 'la' set but not used [-Wunused-but-set-variable]
  223 |         ll res=-1,la=0,ra=0;
      |                   ^~
candies.cpp:223:24: warning: variable 'ra' set but not used [-Wunused-but-set-variable]
  223 |         ll res=-1,la=0,ra=0;
      |                        ^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 3 ms 14680 KB Output is correct
4 Correct 4 ms 14680 KB Output is correct
5 Correct 7 ms 14680 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1165 ms 44564 KB Output is correct
2 Correct 1172 ms 44564 KB Output is correct
3 Correct 1205 ms 44552 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Correct 149 ms 40528 KB Output is correct
3 Correct 324 ms 18240 KB Output is correct
4 Correct 1073 ms 44560 KB Output is correct
5 Correct 1060 ms 44564 KB Output is correct
6 Correct 1094 ms 44552 KB Output is correct
7 Correct 1064 ms 44624 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 102 ms 38160 KB Output is correct
4 Correct 323 ms 17212 KB Output is correct
5 Correct 962 ms 40976 KB Output is correct
6 Correct 967 ms 41380 KB Output is correct
7 Correct 974 ms 41364 KB Output is correct
8 Correct 930 ms 40616 KB Output is correct
9 Correct 939 ms 40804 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 3 ms 14680 KB Output is correct
4 Correct 4 ms 14680 KB Output is correct
5 Correct 7 ms 14680 KB Output is correct
6 Correct 1165 ms 44564 KB Output is correct
7 Correct 1172 ms 44564 KB Output is correct
8 Correct 1205 ms 44552 KB Output is correct
9 Correct 3 ms 14424 KB Output is correct
10 Correct 149 ms 40528 KB Output is correct
11 Correct 324 ms 18240 KB Output is correct
12 Correct 1073 ms 44560 KB Output is correct
13 Correct 1060 ms 44564 KB Output is correct
14 Correct 1094 ms 44552 KB Output is correct
15 Correct 1064 ms 44624 KB Output is correct
16 Correct 3 ms 14424 KB Output is correct
17 Correct 3 ms 14428 KB Output is correct
18 Correct 102 ms 38160 KB Output is correct
19 Correct 323 ms 17212 KB Output is correct
20 Correct 962 ms 40976 KB Output is correct
21 Correct 967 ms 41380 KB Output is correct
22 Correct 974 ms 41364 KB Output is correct
23 Correct 930 ms 40616 KB Output is correct
24 Correct 939 ms 40804 KB Output is correct
25 Incorrect 3 ms 14424 KB Output isn't correct
26 Halted 0 ms 0 KB -