oj.uz

답안 #436857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
436857 2021-06-25T06:00:03 Z blue 사탕 분배 (IOI21_candies) C++17
27 / 100
 751 ms 42792 KB 
#include "candies.h"
#include <vector>
using namespace std;

/*
Consider 'machines' of √Q updates.

Each machine has three numbers a, b and c such that
-> If <= a candies are inserted, a+c candies are obtained.
-> If >= b candies are inserted, b+c candies are obtained.
-> If I candies are inserted, where a <= I <= b, I+c candies are obtained.

To compute the numbers of a machine:
- Pass 0 through the machine to get l
- Pass INF through the machine to get r
- r-l = b-a


*/
int lim; //GOOD

struct machine //GOOD
{
    int a;
    int b;
    int c;

    int res(int u) //GOOD
    {
        if(u < a) return a+c;
        else if(a <= u && u <= b) return u+c;
        else return b+c;
    }
};

machine get_machine(int v)
{
    int a, b, c;
    c = v;
    if(v > 0)
    {
        a = 0;
        b = max(0, lim - v);
    }
    else
    {
        a = min(-v, lim);
        b = lim;
    }
    return machine{a, b, c};
}

machine combine(machine A, machine B)
{
    /*
        1. A.out and B.in are disjoint
            1.1     A.out is below B.in
            1.2     A.out is above B.in
        2. A.out and B.in are not disjoint
            2.1     A.out is a superset of B.in
            2.2     A.out is a subset of B.in
            2.3     A.out is below B.in
            2.4     A.out is above B.in
    */

    int a, b, c;


    if(A.b + A.c < B.a) //1.1
    {
        a = 0;
        b = 0;
        c = B.a + B.c;
    }
    else if(A.a + A.c > B.b)
    {
        a = 0;
        b = 0;
        c = B.b + B.c;
    }
    else
    {
        if(A.a + A.c <= B.a && B.b <= A.b + A.c)
        {
            a = B.a - A.c;
            b = B.b - A.c;
            c = A.c + B.c;
        }
        else if(B.a <= A.a + A.c && A.b + A.c <= B.b)
        {
            a = A.a;
            b = A.b;
            c = A.c + B.c;
        }
        else if(A.a + A.c <= B.a)
        {
            a = B.a - A.c;
            b = A.b;
            c = A.c + B.c;
        }
        else
        {
            a = A.a;
            b = B.b - A.c;
            c = A.c + B.c;
        }
    }

    return machine{a, b, c};
}

machine empty_machine()
{
    return machine{0, lim, +0};
}

struct segtree
{
    int l;
    int r;
    machine x = empty_machine();

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void update(int I, machine X)
    {
        if(I < l || r < I) return;
        else if(l == r) x = X;
        else
        {
            left->update(I, X);
            right->update(I, X);
            x = combine(left->x, right->x);
        }
    }

    int pass_input(int H)
    {
        return x.res(H);
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    int N = c.size();
    int Q = l.size();

    lim = c[0];

    segtree S(0, Q);

    vector<int> insertions[N], removals[N];
    for(int i = 0; i < Q; i++)
    {
        insertions[ l[i] ].push_back(i);
        removals[ r[i] ].push_back(i);
    }

    vector<int> res(N, 0);
    for(int i = 0; i < N; i++)
    {
        for(int o: insertions[i])
        {
            S.update(o, get_machine(v[o]));
        }

        res[i] = S.pass_input(0);

        for(int o: removals[i])
        {
            S.update(o, empty_machine());
        }
    }

    return res;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 487 ms 26832 KB Output is correct
3 Correct 72 ms 13472 KB Output is correct
4 Correct 751 ms 42688 KB Output is correct
5 Correct 751 ms 42692 KB Output is correct
6 Correct 725 ms 42692 KB Output is correct
7 Correct 718 ms 42692 KB Output is correct

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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