제출 #813293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
813293		AbdelmagedNour	사탕 분배 (IOI21_candies)	C++17	30 / 100	5095 ms	41160 KiB

candies

#include <bits/stdc++.h>
//#include "grader.cpp"
#include "candies.h"
using namespace std;
typedef int ll;
struct SegTree{
    struct node{
        ll mne=0,mxe=0,mnf=0,mxf=0;
    }tree[1<<19],treeE[1<<19],treeF[1<<19];
    ll lazy[1<<19][3];
    int sz;
    node op(node const&a,node const&b){
        node res;
        res.mne=min(a.mne,b.mne);
        res.mxe=max(a.mxe,b.mxe);
        res.mnf=min(a.mnf,b.mnf);
        res.mxf=max(a.mxf,b.mxf);
        return res;
    }
    void putTag(int p,int tag,ll val=0){
        if(tag==0)lazy[p][0]+=val;
        if(tag==1)lazy[p][0]=lazy[p][2]=0,lazy[p][1]=1;
        if(tag==2)lazy[p][0]=lazy[p][1]=0,lazy[p][2]=1;
    }
    void add(int p,ll v){
        tree[p].mne+=v;
        tree[p].mxe+=v;
        tree[p].mnf-=v;
        tree[p].mxf-=v;
        lazy[p][0]+=v;
    }
    void add(node&p,ll v){
        p.mne+=v;
        p.mxe+=v;
        p.mnf-=v;
        p.mxf-=v;
    }
    void push(int p){
        for(auto ch:{p*2+1,p*2+2}){
            if(lazy[p][1])tree[ch]=treeF[ch],putTag(ch,1);//full
            if(lazy[p][2])tree[ch]=treeE[ch],putTag(ch,2);//empty
            if(lazy[p][0])add(ch,lazy[p][0]);
        }
        memset(lazy[p],0,sizeof(lazy[p]));
    }
    bool Full(node p,ll v){
        add(p,v);
        return p.mnf<=0&&p.mxf<=0;
    }
    bool Empty(node p,ll v){
        add(p,v);
        return p.mne<=0&&p.mxe<=0;
    }
    bool OK(node p,ll v){
        add(p,v);
        return min({p.mne,p.mxe,p.mnf,p.mxf})>=0;
    }
    void build(int l,int r,int p,vector<int>&c){
        if(l==r){
            tree[p].mne=tree[p].mxe=0;
            tree[p].mnf=tree[p].mxf=c[l];
            treeE[p]=tree[p];
            treeF[p].mne=treeF[p].mxe=c[l];
            treeF[p].mnf=treeF[p].mxf=0;
            return;
        }
        int md=(l+r)>>1;
        build(l,md,p*2+1,c);
        build(md+1,r,p*2+2,c);
        tree[p]=op(tree[p*2+1],tree[p*2+2]);
        treeF[p]=op(treeF[p*2+1],treeF[p*2+2]);
        treeE[p]=op(treeE[p*2+1],treeE[p*2+2]);
    }
    void init(int n,vector<int>c){
        sz=n;
        build(0,sz-1,0,c);
    }
    void update(int l,int r,int p,int l_q,int r_q,ll v){
        if(l>r_q||r<l_q)return;
        if(l>=l_q&&r<=r_q){
            if(Full(tree[p],v)){
                tree[p]=treeF[p];
                putTag(p,1);
                return;
            }else if(Empty(tree[p],v)){
                tree[p]=treeE[p];
                putTag(p,2);
                return;
            }else if(OK(tree[p],v)){
                add(p,v);
                return;
            }
        }
        push(p);
        int md=(l+r)>>1;
        update(l,md,p*2+1,l_q,r_q,v);
        update(md+1,r,p*2+2,l_q,r_q,v);
        tree[p]=op(tree[p*2+1],tree[p*2+2]);
    }
    void update(int l,int r,ll v){
        update(0,sz-1,0,l,r,v);
    }
    int get(int l,int r,int p,int idx){
        if(l==r){
            return tree[p].mne;
        }
        push(p);
        int md=(l+r)>>1;
        if(md>=idx)return get(l,md,p*2+1,idx);
        else return get(md+1,r,p*2+2,idx);
    }
    int get(int idx){
        return get(0,sz-1,0,idx);
    }
}tree;
vector<int>distribute_candies(vector<int>c,vector<int>l,vector<int>r,vector<int>v){
    int n=c.size();
    tree.init(n,c);
    for(int i=0;i<l.size();i++)tree.update(l[i],r[i],v[i]);
    vector<int>ans(n);
    for(int i=0;i<n;i++)ans[i]=tree.get(i);
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:119:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i=0;i<l.size();i++)tree.update(l[i],r[i],v[i]);
      |                 ~^~~~~~~~~

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