oj.uz

답안 #1048929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1048929 2024-08-08T11:17:26 Z amine_aroua 사탕 분배 (IOI21_candies) C++17
0 / 100
 65 ms 7360 KB 
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
int M;
const int BASE = (1<<3);
#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 = -1;
    }
}
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].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].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);
}
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();
    M = c[0];
    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] = get(i);
    }
    return ret;
}

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 65 ms 7360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -