Submission #415979

#	Time	Username	Problem	Language	Result	Execution time	Memory
415979		iulia2100	Cake 3 (JOI19_cake3)	C++14	24 / 100	4053 ms	136204 KiB

cake3

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

using namespace std;

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

const int N = 2e5 + 5;

int n, m;

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

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

namespace segment_tree  {

    struct nod  {
        vector <long long> 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;
                }
            }
            long long sum = 0;
            for (auto it : a[i].val) {
                sum += it;
                a[i].sp.push_back(sum);
            }
        }
    }

    long long nr_bigger(int nod, long long 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;
    }

    long long sum_bigger(int nod, long long 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;
    }

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

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

    long long 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;
                long long 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();
    }
}


long long 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];
long long 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;
    ans[poz] = -1;
    for (int i = max(st, poz + m - 1); i <= dr; ++i)  {
        long long 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] != -1 ? ans[poz] : dr), l, poz - 1);
    if (poz != r)
        find_ans((r + poz) / 2, (ans[poz] != -1 ? ans[poz] : st), dr, poz + 1, r);
}

namespace brut    {

    priority_queue <long long> pq;

    long long brut() {
        long long sum = 0, ans = -1e18;
        for (int i = 1; i <= n; ++i)    {
            sum = 0;
            while (!pq.empty())
                pq.pop();
            for (int j = i; j <= n; ++j)    {
                pq.push(- v[j].v);
                sum += v[j].v;
                while (pq.size() > m)   {
                    sum += pq.top();
                    pq.pop();
                }
                if (pq.size() == m)
                    ans = max(ans, sum - 2 * (v[j].c - v[i].c));
            }
        }
        return ans;
    }
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)    {
        cin >> v[i].v >> v[i].c;
        Max[i] = -1e18;
    }
    sort (v + 1, v + n + 1, cmp);
    if (n <= 2000)  {
        cout << brut::brut();
        return 0;
    }
//    for (int i = 1; i <= n; ++i)    {
//        cout << v[i].v << ' ' << v[i].c << '\n';
//    }
    segment_tree::init();

    find_ans((n + 1) / 2, 1, n, 1, n);
    long long ANS = -1e18;
    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:37:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   37 |                 if (p2 == sz || p1 < sz && a[i + i].val[p1] > a[i + i + 1].val[p2])  {
cake3.cpp: In function 'void find_ans(int, int, int, int, int)':
cake3.cpp:157:60: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  157 |     if (ans[poz] || l > r || poz < l || r < poz || st == 0 && dr == 0 || viz[poz])
      |                                                    ~~~~~~~~^~~~~~~~~~
cake3.cpp: In function 'long long int brut::brut()':
cake3.cpp:187:34: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  187 |                 while (pq.size() > m)   {
      |                        ~~~~~~~~~~^~~
cake3.cpp:191:31: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  191 |                 if (pq.size() == m)
      |                     ~~~~~~~~~~^~~~
cake3.cpp: In function 'long long int segment_tree::Query(int, int)':
cake3.cpp:126:5: warning: control reaches end of non-void function [-Wreturn-type]
  126 |     }
      |     ^

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