Submission #1048223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048223		vjudge1	Distributing Candies (IOI21_candies)	C++17	100 / 100	182 ms	38364 KiB

candies

#include "candies.h"

#include<bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
int C,Kof[200100];
VI ans;
struct segtree{
    struct DATA{
        long long prfmn,prfmx,sum;
        DATA(long long k){
            prfmn=min(0ll,k),
            prfmx=max(0ll,k),sum=k;
        }
        DATA(){
            prfmn=prfmx=sum=0;
        }
        DATA(DATA a,DATA b){ sum=a.sum+b.sum;
            prfmn=min(a.prfmn,b.prfmn+a.sum);
            prfmx=max(a.prfmx,b.prfmx+a.sum);
        }
    } T[1<<19];
    void Add(int i,int l,int r,int p,int v){
        if(l==r) return void(T[i]=DATA(T[i].sum+v));
        if(l+r>>1>=p) Add(i*2,l,l+r>>1,p,v);
        else Add(i*2+1,l+r+2>>1,r,p,v);
        T[i]=DATA(T[i*2],T[i*2+1]);
    }
    int getans(DATA k,int b){
        return (b?k.prfmx>C:k.prfmn>=-C)?C+k.sum-k.prfmx:k.sum-k.prfmn;
    }
    int Qry(int i,int l,int r,DATA prv){
        if(l==r) return getans(DATA(T[i],prv),T[i].sum>=0);
        DATA c=DATA(T[i*2+1],prv);
        if(c.prfmx-c.prfmn<=C)
            return Qry(i*2,l,l+r>>1,c);
        return Qry(i*2+1,l+r+2>>1,r,prv);
    }
} seg;
vector<pair<int,int>> stuf[200100];
VI distribute_candies(VI c,VI l,VI r,VI v) {
    int n=c.size(),q=l.size();
    for(int i=0;i<q;i++)
        stuf[l[i]].push_back({i+1,v[i]}),
        stuf[r[i]+1].push_back({i+1,-v[i]});
    for(int i=0;i<n;i++){
        for(auto[a,b]:stuf[i])
            seg.Add(1,0,q,a,b);
        C=c[i];
        ans.push_back(seg.Qry(1,0,q,seg.T[0]));
    }
    return ans;
}

Compilation message (stderr)

candies.cpp: In member function 'void segtree::Add(int, int, int, int, int)':
candies.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         if(l+r>>1>=p) Add(i*2,l,l+r>>1,p,v);
      |            ~^~
candies.cpp:25:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         if(l+r>>1>=p) Add(i*2,l,l+r>>1,p,v);
      |                                 ~^~
candies.cpp:26:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         else Add(i*2+1,l+r+2>>1,r,p,v);
      |                        ~~~^~
candies.cpp: In member function 'int segtree::Qry(int, int, int, segtree::DATA)':
candies.cpp:36:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |             return Qry(i*2,l,l+r>>1,c);
      |                              ~^~
candies.cpp:37:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         return Qry(i*2+1,l+r+2>>1,r,prv);
      |                          ~~~^~

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