Submission #1049049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049049		Unforgettablepl	Distributing Candies (IOI21_candies)	C++17	0 / 100	208 ms	23016 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

int lim;
const int INF = 1e9;

struct node{
    int maxi,max2,mini,min2,lazy;
    node():maxi(0),max2(-INF),mini(0),min2(INF),lazy(0){}
    node(node left,node right):maxi(0),max2(-INF),mini(0),min2(INF),lazy(0){
        maxi = max(left.maxi,right.maxi);
        if(left.maxi!=maxi)max2=max(max2,left.maxi);
        else max2=max(max2,left.max2);
        if(right.maxi!=maxi)max2=max(max2,right.maxi);
        else max2=max(max2,right.max2);
        mini = min(left.mini,right.mini);
        if(left.mini!=mini)min2=min(min2,left.mini);
        else min2=min(min2,left.min2);
        if(right.mini!=mini)min2=min(min2,right.mini);
        else min2=min(min2,right.min2);
    }
    bool applylazy(){
        mini+=lazy;
        min2+=lazy;
        maxi+=lazy;
        max2+=lazy;
        if(lazy<0){
            if(min2<0)return false;
            mini=max(mini,0);
            max2=max(max2,0);
            maxi=max(maxi,0);
            return true;
        } else {
            if(max2>lim)return false;
            maxi=min(lim,maxi);
            min2=min(lim,min2);
            mini=min(lim,mini);
            return true;
        }
    }
};

struct segtree{
    vector<node> tree;
    int n;
    segtree(int n):n(n),tree(4*n){}
    void update(int qX,int qL,int qR,int L,int R,int x){
        if(tree[x].lazy){
            tree[x].applylazy();
            if(L!=R){
                tree[2*x].lazy+=qX;
                tree[2*x+1].lazy+=qX;
            }
            tree[x].lazy=0;
        }
        if(qR<L or R<qL)return;
        if(qL<=L and R<=qR){
            tree[x].lazy=qX;
            if(tree[x].applylazy()){
                if(L!=R){
                    tree[2*x].lazy+=qX;
                    tree[2*x+1].lazy+=qX;
                }
                tree[x].lazy=0;
                return;
            }
            tree[x].lazy=0;
        }
        int mid = (L+R)/2;
        update(qX,qL,qR,L,mid,2*x);
        update(qX,qL,qR,mid+1,R,2*x+1);
        tree[x]={tree[2*x],tree[2*x+1]};
    }
    void update(int qX,int qL,int qR){
        update(qX,qL,qR,1,n,1);
    }
    int get(int qX,int L,int R,int x){
        if(qX<L or R<qX)return 0;
        if(tree[x].lazy){
            tree[x].applylazy();
            if(L!=R){
                tree[2*x].lazy+=qX;
                tree[2*x+1].lazy+=qX;
            }
            tree[x].lazy=0;
        }
        if(L==R){
            return tree[x].maxi;
        }
        int mid = (L+R)/2;
        return get(qX,L,mid,2*x)+get(qX,mid+1,R,2*x+1);
    }
    int get(int qX){
        return get(qX,1,n,1);
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v){
    int n = c.size();
    int q = v.size();
    lim = c[0];
    segtree seg(n);
    for(int i=0;i<q;i++){
        seg.update(v[i],l[i]+1,r[i]+1);
    }
    vector<int> s(n);
    for(int i=0;i<n;i++)s[i]=seg.get(i+1);
    return s;
}

Compilation message (stderr)

candies.cpp: In constructor 'segtree::segtree(int)':
candies.cpp:46:9: warning: 'segtree::n' will be initialized after [-Wreorder]
   46 |     int n;
      |         ^
candies.cpp:45:18: warning:   'std::vector<node> segtree::tree' [-Wreorder]
   45 |     vector<node> tree;
      |                  ^~~~
candies.cpp:47:5: warning:   when initialized here [-Wreorder]
   47 |     segtree(int n):n(n),tree(4*n){}
      |     ^~~~~~~

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