Submission #615446

#	Time	Username	Problem	Language	Result	Execution time	Memory
615446		ArsBud	Fountain (eJOI20_fountain)	C++14	0 / 100	19 ms	2284 KiB

fountain

#include <iostream>

using namespace std;

int N, Q, k, y = 0, n, v, vid, r;
int m[200005], i[100005], t[100005];

void F(int x)
{
//    cout << "y = " << y << ", x = " << x << ", i[y] = " << i[y] << ", i[x] = " << i[x] << ", m[y] = " << m[y] << ", m[x] = " << m[x] << '\n';
    if(i[y] < i[x])
    {
        m[y] = x;
        return;
    }
    if(m[y] > 0 || m[x] <= 0)
    {
        if(x == N)
        {
            m[y] = -1;
        }
        return;
    }
    F(m[x]);
}

void F1(int w)
{
//    cout << "w = " << w << ", v = " << v << ", t[w] = " << t[w] << ", n = " << n << '\n';
    if(t[w] >= v)
    {
        v = 0;
        n = w;
        return;
    }
    if(v > t[w] && m[w] == -1)
    {
        n = -1;
        return;
    }
    v -= t[w];
//    cout << "v = " << v << ", m[w] = " << m[w] << '\n';
    F1(m[w]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> Q;
    r = N / 2;
    int g;
    for(int a = 0; a < N; a++)
    {
        cin >> i[a] >> t[a];
        if(i[a] > i[a - 1])
        {
            g++;
        }
    }
//    cout << "g == N\n";
    if(g == N)
    {
        t[-1]= 0;
//        cout << "t[-1] = " << t[-1] << '\n';
        for(int a = 0; a < N; a++)
        {
            t[a] += t[a - 1];
        }
        for(int a = 0; a < Q; a++)
        {
//            cout << "a = " << a << '\n';
            int e, h;
//            cout << "e = " << e << ", h = " << h << '\n';
            cin >> e >> h;
//            cout << "e = " << e << ", h = " << h << '\n';
            vid = h - 1;
            r = h / 2;
//            cout << "vid = " << vid << ", r = " << r << ", e = " << e << '\n';
            while(e > 0)
            {
//                cout << "e = " << e << ", t[vid] = " << t[vid] << '\n';
                if(t[vid] > e)
                {
                    vid -= max(1, r / 2);
//                    cout << "vid = " << vid << ", n = " << n << ", t[n] = " << t[n] << '\n';
                    if(vid < h - 1 && e < t[h - 1])
                    {
//                        cout << h << '\n';
                        break;
                    }
                    else
                    {
                        vid = h - 1;
                    }
                }
                if(t[vid] < e)
                {
                    vid += max(1, r / 2);
                }
                if(t[vid] >= e && t[vid - 1] < e)
                {
//                    cout << vid + 1 << '\n';
                    break;
                }
                if(t[vid] < e && vid >= N - 1)
                {
//                    cout << 0 << '\n';
                    break;
                }
            }
        }
        return 0;
    }
    m[N - 1] = -1;
    for(int a = N - 2; a >= 0; a--)
    {
//        cout << "a = " << a << ", i[a] = " << i[a] << ", i[a + 1] = " << i[a + 1] << '\n';
        if(i[a] < i[a + 1])
        {
            m[a] = a + 1;
//            cout << "m[a] = " << m[a] << '\n';
        }
        else
        {
            y = a;
            F(a + 2);
            if(m[a] == 0)
            {
                m[a] = N - 1;
            }
//            cout << "m[a] = " << m[a] << '\n';
        }
    }
//    cout << "ATS : \n";
    for(int a = 0; a < Q; a++)
    {
        cin >> n >> v;
        n--;
        F1(n);
//        cout << "GRIZO\n";
        if(v < 0)
        {
            cout << 0 << '\n';
        }
        else
        {
            cout << n + 1 << '\n';
        }
    }
//    for(int a = 0; a < N; a++)
//    {
//        cout << "a = " << a << ", m[a] = " << m[a] << '\n';
//    }
    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:65:13: warning: array subscript -1 is below array bounds of 'int [100005]' [-Warray-bounds]
   65 |         t[-1]= 0;
      |         ~~~~^
fountain.cpp:6:27: note: while referencing 't'
    6 | int m[200005], i[100005], t[100005];
      |                           ^
fountain.cpp:63:5: warning: 'g' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     if(g == N)
      |     ^~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40