Submission #104901

#	Time	Username	Problem	Language	Result	Execution time	Memory
104901		daili	Cake (CEOI14_cake)	C++14	0 / 100	2055 ms	7136 KiB

cake

#include <bits/stdc++.h>

using namespace std;

int sim(vector<int>& deli , int a, int b)
{
    int eaten = 1;
    a--; b--;

    if (a == b)
    {
        return 0;
    }

    int currL = a;
    int currR = a;

    while(true)
    {
        int L = 99999999;
        if (currL > 0)
        {
            L = deli[currL - 1];
        }

        int R = 99999999;
        if (currR < deli.size() - 1)
        {
            R = deli[currR + 1];
        }

        if (L < R)
        {
            if (currL - 1 == b)
            {
                return eaten;
            }
            currL--;
        }
        else
        {
            if (currR + 1 == b)
            {
                return eaten;
            }
            currR++;
        }
        eaten++;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, a;
    cin >> n >> a;

    vector<pair<int,int>> copy1;
    vector<int> deli;
    map<int,int> top10m;

    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        deli.push_back(x);
        copy1.push_back({x, i});
    }

    sort(copy1.begin(), copy1.end());
    vector<int> top10;
    for (int i = copy1.size() - 1; i >= 0 && i >= n-10; i--)
    {
        top10m[copy1[i].second] = i;
        top10.push_back(copy1[i].second);
    }

    int q;
    cin >> q;

    while(q--)
    {
        char type;
        cin >> type;

        if (type == 'E')
        {
            int id, e;
            cin >> id >> e;
            e--; id--;
            for (int i = 0; i < e; i++)
            {
                deli[top10[i]]++;
            }

            if (!top10m.count(id))
            {
              top10m.erase(top10m.find(top10.back()));
              top10m[id] = e;
              for (int i = top10.size()-1; i > e; i--)
              {
                  top10[i] = top10[i-1];
              }
            }
            else
            {
              for (int i = top10m[id]; i > e; i--)
              {
                  top10[i] = top10[i-1];
              }
            }

            top10[e] = id;
            deli[id] = deli[top10[e+1]] + 1;
        }
        else
        {
            int b;
            cin >> b;
            int res = sim(deli, a, b);
            cout << res << "\n";
        }
    }


}

Compilation message (stderr)

cake.cpp: In function 'int sim(std::vector<int>&, int, int)':
cake.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (currR < deli.size() - 1)
             ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 50