oj.uz

Submission #1049008

# Submission time Handle Problem Language Result Execution time Memory
1049008 2024-08-08T11:58:57 Z amine_aroua Distributing Candies (IOI21_candies) C++17
35 / 100
 212 ms 15700 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Incorrect 1 ms 8536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 15576 KB Output is correct
2 Correct 157 ms 15576 KB Output is correct
3 Correct 133 ms 15624 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 81 ms 13312 KB Output is correct
3 Correct 36 ms 12100 KB Output is correct
4 Correct 144 ms 15700 KB Output is correct
5 Correct 172 ms 15696 KB Output is correct
6 Correct 212 ms 15680 KB Output is correct
7 Correct 170 ms 15696 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Incorrect 1 ms 8536 KB Output isn't correct
3 Halted 0 ms 0 KB -