oj.uz

Submission #853099

# Submission time Handle Problem Language Result Execution time Memory
853099 2023-09-23T12:20:41 Z onepunchac168 Distributing Candies (IOI21_candies) C++17
67 / 100
 1203 ms 47080 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];
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];
        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];
        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);
        }
        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:214:19: warning: variable 'la' set but not used [-Wunused-but-set-variable]
  214 |         ll res=-1,la=0,ra=0;
      |                   ^~
candies.cpp:214:24: warning: variable 'ra' set but not used [-Wunused-but-set-variable]
  214 |         ll res=-1,la=0,ra=0;
      |                        ^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 13148 KB Output is correct
4 Correct 3 ms 13148 KB Output is correct
5 Correct 6 ms 13148 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1122 ms 42984 KB Output is correct
2 Correct 1193 ms 47080 KB Output is correct
3 Correct 1203 ms 46904 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 171 ms 38912 KB Output is correct
3 Correct 326 ms 12672 KB Output is correct
4 Correct 994 ms 43008 KB Output is correct
5 Correct 1049 ms 43004 KB Output is correct
6 Correct 1064 ms 43016 KB Output is correct
7 Correct 1061 ms 43004 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 93 ms 39416 KB Output is correct
4 Correct 307 ms 16764 KB Output is correct
5 Correct 952 ms 42924 KB Output is correct
6 Correct 938 ms 44240 KB Output is correct
7 Correct 963 ms 44296 KB Output is correct
8 Correct 923 ms 43168 KB Output is correct
9 Correct 907 ms 44292 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 13148 KB Output is correct
4 Correct 3 ms 13148 KB Output is correct
5 Correct 6 ms 13148 KB Output is correct
6 Correct 1122 ms 42984 KB Output is correct
7 Correct 1193 ms 47080 KB Output is correct
8 Correct 1203 ms 46904 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 171 ms 38912 KB Output is correct
11 Correct 326 ms 12672 KB Output is correct
12 Correct 994 ms 43008 KB Output is correct
13 Correct 1049 ms 43004 KB Output is correct
14 Correct 1064 ms 43016 KB Output is correct
15 Correct 1061 ms 43004 KB Output is correct
16 Correct 2 ms 12888 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct
18 Correct 93 ms 39416 KB Output is correct
19 Correct 307 ms 16764 KB Output is correct
20 Correct 952 ms 42924 KB Output is correct
21 Correct 938 ms 44240 KB Output is correct
22 Correct 963 ms 44296 KB Output is correct
23 Correct 923 ms 43168 KB Output is correct
24 Correct 907 ms 44292 KB Output is correct
25 Incorrect 2 ms 12892 KB Output isn't correct
26 Halted 0 ms 0 KB -