Submission #443483

#	Time	Username	Problem	Language	Result	Execution time	Memory
443483		leinad2	Distributing Candies (IOI21_candies)	C++17	100 / 100	2923 ms	38436 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
long long mx[800010], mn[800010], lazy[800010], inf=9000000000000000000;
vector<pair<int, int> >upd[200010];
void busy(int id)
{
    lazy[id*2]+=lazy[id];
    lazy[id*2+1]+=lazy[id];
    mx[id*2]+=lazy[id];
    mx[id*2+1]+=lazy[id];
    mn[id*2]+=lazy[id];
    mn[id*2+1]+=lazy[id];
    lazy[id]=0;
}
void update(int id, int s, int e, int l, int r, int v)
{
    if(e<l||r<s)return;
    if(l<=s&&e<=r)
    {
        mx[id]+=v;
        mn[id]+=v;
        lazy[id]+=v;
        return;
    }
    int m=s+e>>1;busy(id);
    update(id*2, s, m, l, r, v);update(id*2+1, m+1, e, l, r, v);
    mx[id]=max(mx[id*2], mx[id*2+1]);
    mn[id]=min(mn[id*2], mn[id*2+1]);
}
long long get1(int id, int s, int e, int l, int r)
{
    if(e<l||r<s)return -inf;
    if(l<=s&&e<=r)return mx[id];
    int m=s+e>>1;busy(id);
    return max(get1(id*2, s, m, l, r), get1(id*2+1, m+1, e, l, r));
}
long long get2(int id, int s, int e, int l, int r)
{
    if(e<l||r<s)return inf;
    if(l<=s&&e<=r)return mn[id];
    int m=s+e>>1;busy(id);
    return min(get2(id*2, s, m, l, r), get2(id*2+1, m+1, e, l, r));
}
vector<int>distribute_candies(vector<int>C, vector<int>l, vector<int>r, vector<int>v)
{
    int n=C.size(), q=l.size(), i, j, k, a, b;
    vector<long long>c;for(i=0;i<n;i++)c.push_back(C[i]);
    for(i=0;i<q;i++)
    {
        upd[l[i]].push_back({v[i], i});
        upd[r[i]+1].push_back({-v[i], i});
    }
    vector<int>ans;ans.resize(n);
    for(i=0;i<n;i++)
    {
        for(j=0;j<upd[i].size();j++)
        {
            a=upd[i][j].first;b=upd[i][j].second;
            update(1, 1, q+1, b+2, q+1, a);
        }
        long long x=get1(1, 1, q+1, 1, q+1)-get2(1, 1, q+1, 1, q+1);
        if(x<=c[i])ans[i]=get1(1, 1, q+1, q+1, q+1)-get2(1, 1, q+1, 1, q+1);
        else
        {
            int a=1, b=q+1;
            while(a<b)
            {
                int m=a+b+1>>1;
                if(get1(1, 1, q+1, m, q+1)-get2(1, 1, q+1, m, q+1)<=c[i])b=m-1;
                else a=m;
            }
            if(get1(1, 1, q+1, a, a)<get2(1, 1, q+1, a+1, q+1))
            {
                ans[i]=c[i]-get1(1, 1, q+1, a+1, q+1)+get1(1, 1, q+1, q+1, q+1);
            }
            else
            {
                ans[i]=get1(1, 1, q+1, q+1, q+1)-get2(1, 1, q+1, a+1, q+1);
            }
        }
    }
    return ans;
}

Compilation message (stderr)

candies.cpp: In function 'void update(int, int, int, int, int, int)':
candies.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int m=s+e>>1;busy(id);
      |           ~^~
candies.cpp: In function 'long long int get1(int, int, int, int, int)':
candies.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int m=s+e>>1;busy(id);
      |           ~^~
candies.cpp: In function 'long long int get2(int, int, int, int, int)':
candies.cpp:42:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int m=s+e>>1;busy(id);
      |           ~^~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(j=0;j<upd[i].size();j++)
      |                 ~^~~~~~~~~~~~~~
candies.cpp:69:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |                 int m=a+b+1>>1;
      |                       ~~~^~
candies.cpp:47:39: warning: unused variable 'k' [-Wunused-variable]
   47 |     int n=C.size(), q=l.size(), i, j, k, a, b;
      |                                       ^

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33