Proficient.
Put your skills to the test.

Problem summary

In a queried index interval, arrange its children in a circle. Child i wants a[i] candies and may take only from its own machine of capacity b[i] and the preceding child’s machine, with wraparound inside the interval. Decide whether every child can be satisfied. Range updates replace all demands in an interval by x and all capacities there by y.

Constraints

1 ≤ N,Q ≤ 200,000; 0 ≤ a[i],b[i],x,y ≤ 10⁹.

Worked example

Official local-grader example; only isValid calls print output.

5
2 0 9 4 1
0 5 4 6 7
7
2 4 4 8 1
1 0 1
2 3 3 4 9
2 1 2 2 2
1 3 4
1 2 2
1 2 4

1
0
1
0

Solution analysis

1. Process a linear segment from left to right. If x candies are available from the preceding machine, satisfying a child while leaving as many candies as possible in its own machine gives f(x)=min(b,x+b−a), provided x≥max(0,a−b). A segment therefore has a summary (need,delta,cap): it is possible for inputs x≥need and its maximum outgoing remainder is min(cap,x+delta). Some segments are impossible even with unlimited incoming supply.
2. Compose adjacent summaries L then R. Feasibility first requires capL≥needR. The combined need is max(needL,needR−deltaL), its delta is deltaL+deltaR, and its cap is min(capR,capL+deltaR). This associative composition is stored in a segment tree. A circle can close exactly when some x≥need satisfies min(cap,x+delta)≥x, which is equivalent to delta≥0 and need≤cap.
3. Lazy range assignment is also constant-time per node. For length s with uniform demand a and capacity b, if b≥a its summary is (0,s(b−a),b). If d=a−b>0, it is (sd,−sd,b−(s−1)d), unless that cap is negative, in which case it is impossible. In the example [0,1] is valid because child 0 can receive two candies from the wrapped final machine. Later [3,4] has total demand 12 but capacity 10 and is invalid.

Why it works

For a given incoming supply, retaining the maximum outgoing remainder cannot hurt any later child. This proves the single-child transfer. Composition follows by requiring the left output to meet the right minimum input and substituting its capped affine expression; thus summaries describe exactly all feasible input supplies. For a cycle, an outgoing remainder at least its assumed incoming supply permits reserving that supply for the first child and discarding surplus. Such a supply exists exactly under delta≥0 and need≤cap, with the cap bounded by the last machine’s capacity. Uniform summaries follow by repeated composition. Consequently the lazy segment tree maintains the exact transfer of every queried interval after every assignment.

Watch out. A length-one interval uses its machine once. Preserve left-to-right summary order. A nonnegative total surplus alone is insufficient; a child can be cut off from remote spare candies.

Judge-library solution: include the official candies.h and compile together with its local grader. It intentionally has no main. The test suite supplies a clearly labeled equivalent local harness.

#include"candies.h"
#include<algorithm>
#include<vector>
// Algorithm: Process a linear segment from left to right.
using namespace std;
namespace{
struct Summary{
    long long need=0;
    long long delta=0;
    long long cap=0;
    bool possible=true;
    bool empty=true;
};
Summary combine(const Summary&left,const Summary&right){
    if(left.empty){
        return right;
    }
    if(right.empty){
        return left;
    }
    Summary result;
    result.empty=false;
    result.possible=left.possible&&right.possible&&left.cap>=right.need;
    if(result.possible){
        result.need=max(left.need,right.need-left.delta);
        result.delta=left.delta+right.delta;
        result.cap=min(right.cap,left.cap+right.delta);
    }
    return result;
}
struct Node{
    Summary value;
    int demand=-1;
    int capacity=0;
};
vector<Node>tree;
int elementCount;
void assignNode(int node,int length,int demand,int capacity){
    Summary result;
    result.empty=false;
    result.delta=1LL*length*(capacity-demand);
    if(capacity>=demand){
        result.need=0;
        result.cap=capacity;
    }
    else{
        long long deficit=demand-capacity;
        result.need=length*deficit;
        result.cap=capacity-(length-1LL)*deficit;
        result.possible=result.cap>=0;
    }
    tree[node].value=result;
    tree[node].demand=demand;
    tree[node].capacity=capacity;
}
void push(int node,int left,int right){
    if(tree[node].demand==-1||left==right){
        return;
    }
    int middle=(left+right)/2;
    assignNode(node*2,middle-left+1,tree[node].demand,tree[node].capacity);
    assignNode(node*2+1,right-middle,tree[node].demand,tree[node].capacity);
    tree[node].demand=-1;
}
void build(int node,int left,int right,const vector<int>&a,const vector<int>&b){
    if(left==right){
        assignNode(node,1,a[left],b[left]);
        return;
    }
    int middle=(left+right)/2;
    build(node*2,left,middle,a,b);
    build(node*2+1,middle+1,right,a,b);
    tree[node].value=combine(tree[node*2].value,tree[node*2+1].value);
}
void change(int node,int left,int right,int from,int to,int a,int b){
    if(from<=left&&right<=to){
        assignNode(node,right-left+1,a,b);
        return;
    }
    push(node,left,right);
    int middle=(left+right)/2;
    if(from<=middle){
        change(node*2,left,middle,from,to,a,b);
    }
    if(to>middle){
        change(node*2+1,middle+1,right,from,to,a,b);
    }
    tree[node].value=combine(tree[node*2].value,tree[node*2+1].value);
}
Summary query(int node,int left,int right,int from,int to){
    if(from<=left&&right<=to){
        return tree[node].value;
    }
    push(node,left,right);
    int middle=(left+right)/2;
    Summary result;
    if(from<=middle){
        result=query(node*2,left,middle,from,to);
    }
    if(to>middle){
        result=combine(result,query(node*2+1,middle+1,right,from,to));
    }
    return result;
}
} // namespace
void init(vector<int>kids,const vector<int>candies){
    elementCount=static_cast<int>(kids.size());
    tree.assign(4*elementCount+4,Node());
    build(1,0,elementCount-1,kids,candies);
}
bool isValid(int left,int right){
    Summary result=query(1,0,elementCount-1,left,right);
    return result.possible&&result.delta>=0&&result.need<=result.cap;
}
void update(int left,int right,int demand,int capacity){
    change(1,0,elementCount-1,left,right,demand,capacity);
}