Submission #927781

#	Time	Username	Problem	Language	Result	Execution time	Memory
927781		boris_mihov	Two Dishes (JOI19_dishes)	C++17	100 / 100	7546 ms	314672 KiB

dishes

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXLOG = 20;
const llong INF = 1e18;

int n, m;
template <typename T>
struct Fenwick
{
    T tree[MAXN];
    void update(int pos, T val)
    {
        for (int idx = pos ; idx <= m ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }

    T query(int pos)
    {
        T res = 0;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }

    int findKthZero(int k)
    {
        int idx = 0;
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (idx + (1 << log) <= m && (1 << log) - tree[idx + (1 << log)] < k)
            {
                idx += (1 << log);
                k -= (1 << log) - tree[idx];
            }
        }

        return idx + 1;
    }

    int findKthOne(int k)
    {
        int idx = 0;
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (idx + (1 << log) <= m && tree[idx + (1 << log)] < k)
            {
                idx += (1 << log);
                k -= tree[idx];
            }
        }

        return idx + 1;
    }
};

struct Fenwick2
{
    llong tree[MAXN];
    void pointUpdate(int pos, llong val)
    {
        for (int idx = pos ; idx <= m + 1 ; idx += idx & (-idx))
        {
            tree[idx] += val;
        }
    }

    llong query(int pos)
    {
        llong res = 0;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }

    void update(int pos, llong value)
    {
        llong val = query(pos);
        pointUpdate(pos, value - val);
        pointUpdate(pos + 1, val - value);
    }

    void rangeUpdate(int l, int r, int value)
    {
        pointUpdate(l, value);
        pointUpdate(r + 1, -value);
    }
};

Fenwick <int> fenwickNext;
Fenwick <llong> fenwickActive;
Fenwick2 dp;

struct Dish
{
    int time;
    llong limit;
    int reward;
    int idx;
    bool type;
};

Dish a[MAXN];
Dish b[MAXN];
llong prefixA[MAXN];
llong prefixB[MAXN];
bool isNext[MAXN];
bool isActive[MAXN];
llong dpBorderM[MAXN];
llong dpBorderN[MAXN];
llong active[MAXN];

int globalRow;
llong findValue(int col)
{
    if (col == m + 1)
    {
        return dp.query(m + 1);
    }

    int cnt = col - 1 - fenwickNext.query(col - 1);
    int pos = m;
    
    if (cnt != m - fenwickNext.query(m))
    {
        pos = fenwickNext.findKthZero(cnt + 1);
    }

    return fenwickActive.query(pos - 1) - fenwickActive.query(col - 1) + dp.query(pos);
}

void fix(int col)
{
    assert(col <= m);
    llong curr = dp.query(col);
    llong next = findValue(col + 1) + active[col];
    int res = isNext[col];
    fenwickNext.update(col, -res);

    int nextVal = 0;
    isNext[col] = false;
    if (curr < next) 
    {
        nextVal = 1;
        isNext[col] = true;
        fenwickNext.update(col, 1);
    }

    dp.update(col, std::max(curr, next));
    if (col > 1)
    {
        int queryRes = fenwickNext.query(col - 1);
        if (queryRes < col - 1)
        {
            int cntZeroesToNow = col - 1 - queryRes;
            int pos = fenwickNext.findKthZero(cntZeroesToNow);
            llong nextVal = findValue(pos + 1) + active[pos];
            if (nextVal > findValue(pos)) fix(pos);
        }

        if (queryRes > 0)
        {
            int cntOnesToNow = queryRes;
            int pos = fenwickNext.findKthOne(cntOnesToNow);
            llong nextVal = findValue(pos + 1) + active[pos];
            if (nextVal > findValue(pos)) fix(pos);
        }
    }
}

void applyUpdate(int to, int val)
{
    dp.rangeUpdate(1, to, val);
}

std::vector <int> activateAt[MAXN];
void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        prefixA[i] = prefixA[i - 1] + a[i].time;
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        prefixB[i] = prefixB[i - 1] + b[i].time;
    }

    for (int aPos = n ; aPos >= 1 ; --aPos)
    {
        dpBorderM[aPos] = dpBorderM[aPos + 1] + (prefixA[aPos - 1] + prefixB[m] + a[aPos].time <= a[aPos].limit ? a[aPos].reward : 0);
    }

    for (int bPos = m ; bPos >= 1 ; --bPos)
    {
        dpBorderN[bPos] = dpBorderN[bPos + 1] + (prefixB[bPos - 1] + prefixA[n] + b[bPos].time <= b[bPos].limit ? b[bPos].reward : 0);
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        int l = 0, r = n + 2, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (prefixA[mid - 1] + prefixB[i] <= b[i].limit) l = mid;
            else r = mid;
        }

        activateAt[l].push_back(i);
    }

    globalRow = n + 1;
    for (int i = 1 ; i <= m ; ++i)
    {
        fenwickNext.update(i, 1);
        isNext[i] = true;
    }

    std::sort(activateAt[n + 1].begin(), activateAt[n + 1].end(), std::greater <int> ());
    for (int i = 1 ; i <= m ; ++i)
    {
        dp.update(i, dpBorderN[i]);
    }
    
    for (const int &idx : activateAt[globalRow])
    {
        active[idx] = b[idx].reward;
        fenwickActive.update(idx, b[idx].reward);
        fix(idx);
    }

    for (globalRow = n ; globalRow >= 1 ; --globalRow)
    {
        for (const int &idx : activateAt[globalRow])
        {
            dp.update(idx, findValue(idx));
        }
    
        int l = 0, r = m + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (prefixA[globalRow] + prefixB[mid - 1] <= a[globalRow].limit) l = mid;
            else r = mid;
        }

        if (l > 0)
        {
            dp.update(l, findValue(l));
        }

        for (const int &idx : activateAt[globalRow])
        {
            active[idx] = b[idx].reward;
            fenwickActive.update(idx, b[idx].reward);
        }


        if (l > 0) activateAt[globalRow].push_back(l);
        applyUpdate(l, a[globalRow].reward);

        dp.update(m + 1, dpBorderM[globalRow]);
        activateAt[globalRow].push_back(m);
        std::sort(activateAt[globalRow].begin(), activateAt[globalRow].end(), std::greater <int> ());

        for (const int &idx : activateAt[globalRow])
        {
            fix(idx);
        }
    }

    globalRow++;
    std::cout << findValue(1) << '\n';
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i].time >> a[i].limit >> a[i].reward;
        a[i].idx = i;
        a[i].type = false;
    }

    for (int i = 1 ; i <= m ; ++i)
    {
        std::cin >> b[i].time >> b[i].limit >> b[i].reward;
        b[i].idx = i;
        a[i].type = true;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

signed main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

dishes.cpp: In function 'void fix(int)':
dishes.cpp:156:9: warning: variable 'nextVal' set but not used [-Wunused-but-set-variable]
  156 |     int nextVal = 0;
      |         ^~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9