Submission #1044289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044289		Unforgettablepl	Distributing Candies (IOI21_candies)	C++17	29 / 100	1771 ms	1550160 KiB

candies

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

pair<bool,int> combine(pair<bool,int> a,pair<bool,int> b){
    if(b.first)return b;
    return {a.first,a.second+b.second};
}

struct node{
    node *left, *right;
    int L,R;
    pair<bool,int> lazy;
    node(int L,int R):L(L),R(R),lazy(true,0),left(nullptr),right(nullptr){}
};

void update(int L,int R,node *curr,pair<bool,int> x){
    if(curr->R<L or R<curr->L)return;
    if(L<=curr->L and curr->R<=R){
        curr->lazy = combine(curr->lazy,x);
        return;
    }
    int mid = (curr->L + curr->R)/2;
    if(curr->left==nullptr)curr->left = new node(curr->L,mid);
    if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
    if(curr->lazy.first or curr->lazy.second){
        curr->left->lazy = combine(curr->left->lazy,curr->lazy);
        curr->right->lazy = combine(curr->right->lazy,curr->lazy);
        curr->lazy = {false,0};
    }
    update(L,R,curr->left,x);
    update(L,R,curr->right,x);
}

int getval(int x,node* curr){
    if(curr->L==curr->R){
        assert(curr->lazy.first);
        if(curr->lazy.second<0)return x+curr->lazy.second+1;
        else return curr->lazy.second;
    }
    int mid = (curr->L + curr->R)/2;
    if(curr->left==nullptr)curr->left = new node(curr->L,mid);
    if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
    if(curr->lazy.first or curr->lazy.second){
        curr->left->lazy = combine(curr->left->lazy,curr->lazy);
        curr->right->lazy = combine(curr->right->lazy,curr->lazy);
        curr->lazy = {false,0};
    }
    if(x<=mid)return getval(x,curr->left);
    else return getval(x,curr->right);
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                               vector<int> r, vector<int> v){
    int n = c.size();
    int q = v.size();
    vector<int> s(n);
    node *head = new node(1,1e9);
    for(int i=0;i<q;i++){
        if(v[i]>0){
            int x = 0;
            for(int jump=536870912;jump;jump/=2){
                if(x+jump>1e9)continue;
                if(getval(x+jump,head)+v[i]>=x+jump)x+=jump;
            }
            if(x)update(1,x,head,{true,-1});
            update(x+1,1e9,head,{false,v[i]});
        } else {
            int x = 0;
            for(int jump=536870912;jump;jump/=2){
                if(x+jump>1e9)continue;
                if(getval(x+jump,head)+v[i]<=0)x+=jump;
            }
            if(x)update(1,x,head,{true,0});
            update(x+1,1e9,head,{false,v[i]});
        }
    }
    for(int i=0;i<n;i++)s[i]=getval(c[i],head);
    return s;
}

Compilation message (stderr)

candies.cpp: In constructor 'node::node(int, int)':
candies.cpp:13:20: warning: 'node::lazy' will be initialized after [-Wreorder]
   13 |     pair<bool,int> lazy;
      |                    ^~~~
candies.cpp:11:11: warning:   'node* node::left' [-Wreorder]
   11 |     node *left, *right;
      |           ^~~~
candies.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     node(int L,int R):L(L),R(R),lazy(true,0),left(nullptr),right(nullptr){}
      |     ^~~~

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