oj.uz

Submission #813391

# Submission time Handle Problem Language Result Execution time Memory
813391 2023-08-07T16:45:14 Z Qingyu Distributing Candies (IOI21_candies) C++17
30 / 100
 5000 ms 41488 KB 
#include <bits/stdc++.h>
//#include "grader.cpp"
#include "candies.h"
using namespace std;
struct SegTree{
    struct node{
        int mne=0,mxe=0,mnf=0,mxf=0;
    }tree[1<<19],treeE[1<<19],treeF[1<<19];
    int 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,int 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,int 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,int 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);//fuint
            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,int v){
        return p.mxf-v<=0;
    }
    bool Empty(node&p,int v){
        return p.mxe+v<=0;
    }
    bool OK(node&p,int v){
        return p.mne+v>=0&&p.mnf-v>=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,int v){
        if(l>r_q||r<l_q)return;
        if(tree[p].mxf==0&&v>0)return;
        if(tree[p].mxe==0&&v<0)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,int 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;
}

Compilation message

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25044 KB Output is correct
2 Correct 10 ms 24916 KB Output is correct
3 Correct 10 ms 24920 KB Output is correct
4 Correct 12 ms 24948 KB Output is correct
5 Correct 32 ms 24992 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5099 ms 40620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24916 KB Output is correct
2 Correct 183 ms 32720 KB Output is correct
3 Correct 81 ms 36780 KB Output is correct
4 Correct 390 ms 41412 KB Output is correct
5 Correct 450 ms 41468 KB Output is correct
6 Correct 432 ms 41488 KB Output is correct
7 Correct 307 ms 41356 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24916 KB Output is correct
2 Correct 10 ms 24916 KB Output is correct
3 Execution timed out 5077 ms 32260 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25044 KB Output is correct
2 Correct 10 ms 24916 KB Output is correct
3 Correct 10 ms 24920 KB Output is correct
4 Correct 12 ms 24948 KB Output is correct
5 Correct 32 ms 24992 KB Output is correct
6 Execution timed out 5099 ms 40620 KB Time limit exceeded
7 Halted 0 ms 0 KB -