Submission #1048136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048136		vjudge1	Distributing Candies (IOI21_candies)	C++17	29 / 100	400 ms	23240 KiB

candies

#include "candies.h"

#include<bits/stdc++.h>
using namespace std;
int CONS, Kof[200100];
vector<int>ans;
struct segtree{
    struct DATA{
        int extreme,dif;
        DATA(){
            extreme=0;
            dif=0;
        }
        DATA(int a,int b){
            extreme=a,dif=b;
        }
        void apply(DATA k){
            if(k.extreme)
                extreme=k.extreme,dif=0;
            dif+=k.dif;
        }
        int q(int K){
            return (extreme>0)*K+dif;
        }
    } T[1<<19];
    void pd(int i){
        T[i*2].apply(T[i]);
        T[i*2+1].apply(T[i]);
        T[i]=DATA();
    }
    void Add(int i,int l,int r,int ll,int rr,int v){
        if(ll<=l&&r<=rr)
            return T[i].apply((DATA){0,v});
        if(ll>r||l>rr) return;
        pd(i);Add(i*2,l,l+r>>1,ll,rr,v);
        Add(i*2+1,l+r+2>>1,r,ll,rr,v);
    }
    void Set(int i,int l,int r,int ll,int rr,int v){
        if(ll<=l&&r<=rr)
            return T[i].apply((DATA){v,0});
        if(ll>r||l>rr) return;
        pd(i);Set(i*2,l,l+r>>1,ll,rr,v);
        Set(i*2+1,l+r+2>>1,r,ll,rr,v);
    }
    int Qry(int i,int l,int r,int p){
        if(l==r) return T[i].q(Kof[l]);
        pd(i);if(l+r>>1>=p)
            return Qry(i*2,l,l+r>>1,p);
        return Qry(i*2+1,l+r+2>>1,r,p);
    }
} seg;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    map<int,int>mp;
    for(auto i:c)
        mp[i];
    int CC=0;
    for(auto&[i,j]:mp)
        Kof[j=++CC]=i;
    CONS=c[0]; 
    int n = c.size(),q=l.size();
    seg.T[1].extreme=-1;
    for(int i=0;i<q;i++) {
        int l=1,r=CC,res=0;
        while(l<=r){
            int mid=l+r>>1;
            int K=seg.Qry(1,1,CC,mid);
            if(v[i]<0){
                if(K<-v[i])
                    l=mid+1,res=mid;
                else r=mid-1;
            } else {
                if(v[i]>Kof[mid]-K)
                    l=mid+1,res=mid;
                else r=mid-1;
            }
        }
        seg.Set(1,1,CC,1,res,v[i]<0?-1:1);
        seg.Add(1,1,CC,res+1,CC,v[i]);
    }
    for(int i=0;i<n;i++)
        ans.push_back(seg.Qry(1,1,CC,mp[c[i]]));
    return ans;
}

Compilation message (stderr)

candies.cpp: In member function 'void segtree::Add(int, int, int, int, int, int)':
candies.cpp:35:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         pd(i);Add(i*2,l,l+r>>1,ll,rr,v);
      |                         ~^~
candies.cpp:36:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         Add(i*2+1,l+r+2>>1,r,ll,rr,v);
      |                   ~~~^~
candies.cpp: In member function 'void segtree::Set(int, int, int, int, int, int)':
candies.cpp:42:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         pd(i);Set(i*2,l,l+r>>1,ll,rr,v);
      |                         ~^~
candies.cpp:43:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         Set(i*2+1,l+r+2>>1,r,ll,rr,v);
      |                   ~~~^~
candies.cpp: In member function 'int segtree::Qry(int, int, int, int)':
candies.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         pd(i);if(l+r>>1>=p)
      |                  ~^~
candies.cpp:48:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |             return Qry(i*2,l,l+r>>1,p);
      |                              ~^~
candies.cpp:49:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         return Qry(i*2+1,l+r+2>>1,r,p);
      |                          ~~~^~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:66:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |             int mid=l+r>>1;
      |                     ~^~

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