Submission #415940

#	Time	Username	Problem	Language	Result	Execution time	Memory
415940		iulia2100	Cake 3 (JOI19_cake3)	C++14	0 / 100	20 ms	37836 KiB

cake3

#include <fstream>
#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;

    void build()    {
        for (int i = start - 1; i; --i) {
            int sz = a[i + i].val.size();
            int p1 = 0, p2 = 0;
            while((p1 < sz || p2 < sz) && p1 + p2 < m) {
                if (p2 == sz || p1 < sz && a[i + i].val[p1] > a[i + i + 1].val[p2])  {
                    a[i].val.push_back(a[i + i].val[p1]);
                    ++p1;
                } else    {
                    a[i].val.push_back(a[i + i + 1].val[p2]);
                    ++p2;
                }
            }
            int sum = 0;
            for (auto it : a[i].val) {
                sum += it;
                a[i].sp.push_back(sum);
            }
        }
    }

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

    int sum_bigger(int nod, int val)   {
        int st = 0, dr = a[nod].val.size() - 1, mij, ans = 0;
        while (st <= dr)    {
            mij = (st + dr) / 2;
            if (a[nod].val[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)  {
    if (r - x + 1 < m || r > n || r < 1 || x > n || x < 1)
        return -1;
    return segment_tree::Query(x, r) - 2 * (v[r].c - v[x].c);
}

int ans[N], Max[N];
bool viz[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 || viz[poz])
        return;
    viz[poz] = true;
    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();

    cout << calc(1, n);
//    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 'void segment_tree::build()':
cake3.cpp:36:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   36 |                 if (p2 == sz || p1 < sz && a[i + i].val[p1] > a[i + i + 1].val[p2])  {
cake3.cpp: In function 'int segment_tree::Query_aint(int, int)':
cake3.cpp:104:5: warning: no return statement in function returning non-void [-Wreturn-type]
  104 |     }
      |     ^
cake3.cpp: In function 'void find_ans(int, int, int, int, int)':
cake3.cpp:155:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  155 |     if (ans[poz] || l > r || poz < l || r < poz || st == 0 && dr == 0 || viz[poz])
      |                                                    ~~~~~~~~^~~~~~~~~~
cake3.cpp: In function 'int segment_tree::Query(int, int)':
cake3.cpp:125:5: warning: control reaches end of non-void function [-Wreturn-type]
  125 |     }
      |     ^

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