oj.uz

Submission #437008

# Submission time Handle Problem Language Result Execution time Memory
437008 2021-06-25T15:29:47 Z blue Distributing Candies (IOI21_candies) C++17
27 / 100
 707 ms 42708 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 empty_machine()
{
    return machine{0, lim, +0};
}

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 || A.a + A.c > B.b) return machine{0, 0, B.res(A.res(0))};
    else return machine{max(A.a, B.a - A.c), min(A.b, B.b - A.c), A.c + B.c};
}

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;
}

Compilation message

candies.cpp: In function 'machine combine(machine, machine)':
candies.cpp:71:9: warning: unused variable 'a' [-Wunused-variable]
   71 |     int a, b, c;
      |         ^
candies.cpp:71:12: warning: unused variable 'b' [-Wunused-variable]
   71 |     int a, b, c;
      |            ^
candies.cpp:71:15: warning: unused variable 'c' [-Wunused-variable]
   71 |     int a, b, c;
      |               ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory 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

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 427 ms 26720 KB Output is correct
3 Correct 73 ms 13492 KB Output is correct
4 Correct 707 ms 42688 KB Output is correct
5 Correct 648 ms 42700 KB Output is correct
6 Correct 673 ms 42692 KB Output is correct
7 Correct 656 ms 42692 KB Output is correct

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

# Verdict Execution time Memory 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 -