Submission #1049008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049008		amine_aroua	Distributing Candies (IOI21_candies)	C++17	35 / 100	212 ms	15700 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
int M;
const int BASE = (1<<18);
#define lc(x) (x<<1)
#define rc(x) (x<<1 | 1)
struct Node
{
    int set , mn , mx , lz;
    Node()
    {
        set = -1 , mn = 0 , mx = 0 , lz = 0;
    }
};
vector<Node> tree(2*BASE , Node());
Node add(Node node , int x)
{
    node.lz+=x;
    node.mx+=x;
    node.mn+=x;
    return node;
}
Node apply(Node node, int x)
{
    node.lz = 0;
    node.mx = x;
    node.mn = x;
    node.set = x;
    return node;
}
void propagate(int node)
{
    if(tree[node].set != -1)
    {
        tree[lc(node)] = apply(tree[lc(node)] , tree[node].set);
        tree[rc(node)] = apply(tree[rc(node)] , tree[node].set);
        tree[node].set = -1;
    }
    if(tree[node].lz)
    {
        tree[lc(node)] = add(tree[lc(node)] , tree[node].lz);
        tree[rc(node)] = add(tree[rc(node)] , tree[node].lz);
        tree[node].lz = 0;
    }
}
void upd(int node , int s , int e , int l , int r , int v)
{
    if(s > r || l > e)
    {
        return;
    }
    if(l <= s && e <= r)
    {
        tree[node] = add(tree[node] , v);
        return;
    }
    int mid = (s + e)>>1;
    propagate(node);
    upd(lc(node) , s , mid , l , r , v);
    upd(rc(node) , mid + 1 , e , l , r , v);
    tree[node].mn = min(tree[lc(node)].mn , tree[rc(node)].mn);
    tree[node].mx = max(tree[lc(node)].mx , tree[rc(node)].mx);
}

void upd(int l , int r , int v)
{
    upd(1 , 0 , BASE - 1 , l , r , v);
}
void minimize(int node , int s , int e)
{
    if(tree[node].mx <= M)
    {
        return;
    }
    if(tree[node].mn >= M)
    {
        tree[node] = apply(tree[node] , M);
        return ;
    }
    if(s == e)
        return ;
    int m = (s + e)>>1;
    propagate(node);
    minimize(lc(node) , s , m);
    minimize(rc(node) , m + 1 , e);
    tree[node].mn = min(tree[lc(node)].mn , tree[rc(node)].mn);
    tree[node].mx = max(tree[lc(node)].mx , tree[rc(node)].mx);
}
void maximize(int node , int s , int e)
{
    if(tree[node].mn >= 0)
    {
        return ;
    }
    if(tree[node].mx <= 0)
    {
        tree[node] = apply(tree[node] , 0);
        return ;
    }
    if(s == e)
        return ;
    int m = (s + e)>>1;
    propagate(node);
    maximize(lc(node) , s , m);
    maximize(rc(node) , m + 1 , e);
    tree[node].mn = min(tree[lc(node)].mn , tree[rc(node)].mn);
    tree[node].mx = max(tree[lc(node)].mx , tree[rc(node)].mx);
}
int get(int node,  int s , int e , int i)
{
    if(s == e)
    {
        assert(tree[node].mn == tree[node].mx);
        return tree[node].mn;
    }
    int mid = (s + e)>>1;
    propagate(node);
    if(i <= mid)
    {
        return get(lc(node) , s , mid , i);
    }
    else
        return get(rc(node) , mid + 1 , e , i);
}
int get(int i)
{
    return get(1 , 0 , BASE - 1 , i);
}
vector<int> brute(vector<int> c , vector<int> l , vector<int> r ,vector<int>v)
{
    int n = (int)c.size();
    int q = (int)l.size();
    vector<int> ret(n);
    M = c[0];
    for(int j = 0 ; j < q ; j++)
    {
        for(int i = l[j] ; i <= r[j] ; i++)
        {
            ret[i]+=v[j];
            ret[i] = min(ret[i],  M);
            ret[i] = max(ret[i] , 0);
        }
    }
    return ret;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    if(n <= 2000 && (int)l.size() <= 2000)
    {
        return brute(c , l , r , v);
    }
    M = *max_element(c.begin() , c.end());
    int q = (int)l.size();
    for(int i = 0 ; i < q ; i++)
    {
        upd(l[i] , r[i] , v[i]);
        if(v[i] > 0)
        {
            minimize(1 , 0 , BASE - 1);
        }
        else
            maximize(1 , 0 , BASE - 1);
        
    }
    vector<int> ret(n);
    for(int i = 0 ;i < n ; i++)
    {
        ret[i] = min(c[i] , get(i));
    }
    return ret;
}

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