oj.uz

Submission #853103

# Submission time Handle Problem Language Result Execution time Memory
853103 2023-09-23T12:25:12 Z onepunchac168 Distributing Candies (IOI21_candies) C++17
67 / 100
 1207 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==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 1197 ms 44552 KB Output is correct
2 Correct 1207 ms 44624 KB Output is correct
3 Correct 1174 ms 44548 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 168 ms 40528 KB Output is correct
3 Correct 325 ms 14232 KB Output is correct
4 Correct 1072 ms 44624 KB Output is correct
5 Correct 1081 ms 44568 KB Output is correct
6 Correct 1143 ms 44624 KB Output is correct
7 Correct 1109 ms 44372 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 14424 KB Output is correct
3 Correct 90 ms 39260 KB Output is correct
4 Correct 310 ms 17220 KB Output is correct
5 Correct 989 ms 40600 KB Output is correct
6 Correct 972 ms 40600 KB Output is correct
7 Correct 994 ms 41232 KB Output is correct
8 Correct 952 ms 40816 KB Output is correct
9 Correct 927 ms 40360 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 1197 ms 44552 KB Output is correct
7 Correct 1207 ms 44624 KB Output is correct
8 Correct 1174 ms 44548 KB Output is correct
9 Correct 3 ms 8536 KB Output is correct
10 Correct 168 ms 40528 KB Output is correct
11 Correct 325 ms 14232 KB Output is correct
12 Correct 1072 ms 44624 KB Output is correct
13 Correct 1081 ms 44568 KB Output is correct
14 Correct 1143 ms 44624 KB Output is correct
15 Correct 1109 ms 44372 KB Output is correct
16 Correct 3 ms 14424 KB Output is correct
17 Correct 3 ms 14424 KB Output is correct
18 Correct 90 ms 39260 KB Output is correct
19 Correct 310 ms 17220 KB Output is correct
20 Correct 989 ms 40600 KB Output is correct
21 Correct 972 ms 40600 KB Output is correct
22 Correct 994 ms 41232 KB Output is correct
23 Correct 952 ms 40816 KB Output is correct
24 Correct 927 ms 40360 KB Output is correct
25 Incorrect 3 ms 14424 KB Output isn't correct
26 Halted 0 ms 0 KB -