Submission #415925

#	Time	Username	Problem	Language	Result	Execution time	Memory
415925		iulia2100	Cake 3 (JOI19_cake3)	C++14	0 / 100	192 ms	262148 KiB

cake3

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//ifstream cin ("idk.in");
//ofstream cout ("idk.out");

const int N = 2e5 + 5;

int n, m;

struct idk  {
    int v, c;
} v[N];

bool cmp(idk x, idk y)  {
    return x.c < y.c;
}

namespace segment_tree  {

    struct nod  {
        vector <int> val, sp;
    } a[4 * N];

    vector <int> noduri;
    int start;

    nod interclasare(nod x, nod y)  {
        nod aux;
        int sz = x.val.size();
        int p1 = 0, p2 = 0;
        while((p1 < sz || p2 < sz) && p1 + p2 < m) {
            if (p2 == sz || p1 < sz && x.val[p1] > y.val[p2])  {
                aux.val.push_back(x.val[p1]);
                ++p1;
            } else    {
                aux.val.push_back(y.val[p2]);
                ++p2;
            }
        }
        int sum = 0;
        for (auto it : aux.val) {
            sum += it;
            aux.sp.push_back(sum);
        }
        return aux;
    }

    void build()    {
        for (int i = start - 1; i; --i) {
            a[i] = interclasare(a[i + i], a[i + i + 1]);
        }
    }

    int nr_bigger(int nod, int val)   {
        vector <int> x = a[nod].val;
        int st = 0, dr = x.size() - 1, mij, ans = 0;
        while (st <= dr)    {
            mij = (st + dr) / 2;
            if (x[mij] >= val)  {
                ans = mij + 1;
                st = mij + 1;
            }
            else dr = mij - 1;
        }
        return ans;
    }

    int sum_bigger(int nod, int val)   {
        vector <int> x = a[nod].val;
        int st = 0, dr = x.size() - 1, mij, ans = 0;
        while (st <= dr)    {
            mij = (st + dr) / 2;
            if (x[mij] >= val)  {
                ans = mij + 1;
                st = mij + 1;
            }
            else dr = mij - 1;
        }
        if (ans == 0)
            return 0;
        return a[nod].sp[ans - 1];
    }

    int nr_noduri(int val)  {
        int ans = 0;
        for (auto it : noduri)  {
            ans += nr_bigger(it, val);
        }
        return ans;
    }

    int sum_noduri(int val)    {
        int ans = 0;
        for (auto it : noduri)  {
            ans += sum_bigger(it, val);
        }
        int aux = nr_noduri(val);
        return ans - (aux - m) * val;
    }

    int Query_aint(int st, int dr)  {
        if (st & 1)
            noduri.push_back(st++);
        if (!(dr & 1))
            noduri.push_back(dr--);
        if (st <= dr)
            Query_aint(st / 2, dr / 2);
    }

    int Query(int st, int dr)   {
        st += start - 1, dr += start - 1;
        noduri.clear();
        Query_aint(st, dr);
        for (auto it : noduri)  {
            int st = 0, dr = a[it].val.size() - 1, mij;
            while (st <= dr)    {
                mij = (st + dr) / 2;
                int aux = nr_noduri(a[it].val[mij]);
                if (aux < m)    {
                    st = mij + 1;
                    continue;
                }
                if (nr_noduri(a[it].val[mij] + 1) < m)  {
                    return sum_noduri(a[it].val[mij]);
                }
                dr = mij - 1;
            }
        }
    }
    void init() {
        start = 1;
        while (start < n)   {
            start <<= 1;
        }

        for (int i = 1; i <= n; ++i)    {
            a[i + start - 1].val.push_back(v[i].v);
            a[i + start - 1].sp.push_back(v[i].v);
        }
        for (int i = n + 1; i <= start; ++i)    {
            a[i + start - 1].val.push_back(0);
            a[i + start - 1].sp.push_back(0);
        }
        build();
    }
}


int calc(int x, int r)  {
    return segment_tree::Query(x, r) - 2 * (v[r].c - v[x].c);
}

int ans[N], Max[N];

void find_ans(int poz, int st, int dr, int l, int r)  {
    if (ans[poz] || l > r || poz < l || r < poz || st == 0 && dr == 0)
        return;
    for (int i = max(st, poz + m - 1); i <= dr; ++i)  {
        int k = calc(poz, i);
        if (k >= Max[poz])   {
            Max[poz] = k;
            ans[poz] = i;
        }
    }
    if (poz != l)
        find_ans((l + poz) / 2, st, ans[poz], l, poz - 1);
    if (poz != r)
        find_ans((r + poz) / 2, ans[poz], dr, poz + 1, r);
}

int main()  {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)    {
        cin >> v[i].v >> v[i].c;
    }
    sort (v + 1, v + n + 1, cmp);
    segment_tree::init();

    find_ans((n + 1) / 2, (n + 1) / 2, n, 1, n);
    int ANS = 0;
    for (int i = 1; i <= n; ++i)    {
        ANS = max(ANS, Max[i]);
    }
    cout << ANS;
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'segment_tree::nod segment_tree::interclasare(segment_tree::nod, segment_tree::nod)':
cake3.cpp:36:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   36 |             if (p2 == sz || p1 < sz && x.val[p1] > y.val[p2])  {
cake3.cpp: In function 'int segment_tree::Query_aint(int, int)':
cake3.cpp:112:5: warning: no return statement in function returning non-void [-Wreturn-type]
  112 |     }
      |     ^
cake3.cpp: In function 'void find_ans(int, int, int, int, int)':
cake3.cpp:160:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  160 |     if (ans[poz] || l > r || poz < l || r < poz || st == 0 && dr == 0)
      |                                                    ~~~~~~~~^~~~~~~~~~
cake3.cpp: In function 'int segment_tree::Query(int, int)':
cake3.cpp:133:5: warning: control reaches end of non-void function [-Wreturn-type]
  133 |     }
      |     ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76