oj.uz

Submission #927728

# Submission time Handle Problem Language Result Execution time Memory
927728 2024-02-15T09:29:48 Z boris_mihov Two Dishes (JOI19_dishes) C++17
10 / 100
 10000 ms 48672 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

#define int long long
typedef long long llong;
const int MAXN = 200000 + 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;
    }
};

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

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 dp[MAXN];

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

    int cnt = col - 1 - fenwickNext.query(col - 1);
    int pos = m;
    
    if (cnt != m - fenwickNext.query(m))
    {
        // std::cout << "IN THE FUCKING IF: " << cnt << ' ' << m << ' ' << fenwickNext.query(m) << '\n';
        // std::cout << "next is\n";
        // for (int i = 1 ; i <= m ; ++i)
        // {
        //     std::cout << fenwickNext.query(i) - fenwickNext.query(i - 1);
        // }

        // std::cout << '\n';

        // std::cout << "lapai\n";
        pos = fenwickNext.findKthZero(cnt + 1);
    }

    // if (col == 3) std::cout << "\n\n      value: " << col << ' ' << m - fenwickNext.query(m) << ' ' << cnt << ' ' << pos << ' ' << fenwickActive.query(pos - 1) - fenwickActive.query(col - 1) + dp[pos] << '\n';
    return fenwickActive.query(pos - 1) - fenwickActive.query(col - 1) + dp[pos];
}

void fix(int col)
{
    // std::cout << "fix: " << col << '\n';
    assert(col <= m);
    llong prevVal = findValue(col);
    llong curr = dp[col];
    llong next = findValue(col + 1) + fenwickActive.query(col) - fenwickActive.query(col - 1);
    // std::cout << "here: " << curr << ' ' << next << '\n';
    int res = fenwickNext.query(col) - fenwickNext.query(col - 1);
    fenwickNext.update(col, -res);

    int nextVal = 0;
    if (curr > next) 
    {
        fenwickNext.update(col, 0); // unessesary
    } else 
    {
        nextVal = 1;
        fenwickNext.update(col, 1);
    }

    // std::cout << "set: " << col << " = " << curr << ' ' << next << '\n';
    dp[col] = std::max(curr, next);
    // std::cout << "fixing previous?: " << dp[col] << ' ' << prevVal << ' ' << fenwickNext.query(col - 1) - fenwickNext.query(col - 2) << '\n';
    if (col > 1 && fenwickNext.query(col - 1) < col - 1)
    {
        // fix(col - 1);
        int cntZeroesToNow = col - 1 - fenwickNext.query(col - 1);
        fix(fenwickNext.findKthZero(cntZeroesToNow));
        // if (prevVal <= dp[col])
        // {
        //     int cntBefore = col - 1 - fenwickNext.query(col - 1);
        //     for (int idx = col - 1 ; idx >= 1 ; --idx)
        //     {
        //         if (fenwickNext.query(idx) - fenwickNext.query(idx - 1) == 0)
        //         {
        //             fix(idx);
        //             return;
        //         }

        //         llong val = findValue(idx);
        //         fix(idx);
        //         llong val2 = findValue(idx);
        //         if (val != val2)
        //         {
        //             assert(fenwickNext.query(idx) - fenwickNext.query(idx - 1) == 0);
        //             exit(0);
        //         }

        //         assert(val == val2);
        //     }
        //     // std::cout << "cnt before: " << cntBefore << '\n';
        //     // if (cntBefore > 0)
        //     // {
        //     //     fix(fenwickNext.findKthZero(cntBefore));
        //     // }
        // } else
        // {
        //     // assert(false);
        //     int cntBefore = fenwickNext.query(col - 1);
        //     // std::cout << "cnt before: " << cntBefore << '\n';
        //     if (cntBefore > 0)
        //     {
        //         fix(fenwickNext.findKthOne(cntBefore));
        //     }
        // }
    }
}

void applyUpdate(int to, int val)
{
    for (int i = 1 ; i <= to ; ++i)
    {
        dp[i] += 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 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);
        // std::cout << "here: " << i << ' ' << l << '\n';
    }

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

    std::sort(activateAt[n + 1].begin(), activateAt[n + 1].end(), std::greater <int> ());
    for (const int &idx : activateAt[globalRow])
    {
        // std::cout << "activate: " << idx << '\n';
        fenwickActive.update(idx, b[idx].reward);
        fix(idx);
    }

    // std::cout << "dp after: " << n + 1 << '\n';
    // for (int i = 1 ; i <= m ; ++i)
    // {
    //     std::cout << findValue(i) << ' ';
    // } 

    // std::cout << '\n';

    for (globalRow = n ; globalRow >= 1 ; --globalRow)
    {
        // std::cout << "      global: " << globalRow << '\n';
        for (const int &idx : activateAt[globalRow])
        {
            dp[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[l] = findValue(l);
        }

        for (const int &idx : activateAt[globalRow])
        {
            // std::cout << "      activate: " << idx << '\n';
            fenwickActive.update(idx, b[idx].reward);
        }

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

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

        // std::cout << "after applying\n";
        // for (int i = 1 ; i <= m ; ++i)
        // {
        //     std::cout << findValue(i) << ' ';
        // } 

        // std::cout << '\n';

        // std::cout << "next is\n";
        // for (int i = 1 ; i <= m ; ++i)
        // {
        //     std::cout << fenwickNext.query(i) - fenwickNext.query(i - 1);
        // }

        // std::cout << '\n';
        for (const int &idx : activateAt[globalRow])
        {
            // std::cout << "fix: " << idx << '\n';
            fix(idx);
            // if (idx > 1) fix(idx - 1);
        }

        // for (int idx = m ; idx >= 1 ; --idx)
        // {
        //     fix(idx);
        // }

        // std::cout << "dp after: " << globalRow << '\n';
        // for (int i = 1 ; i <= m ; ++i)
        // {
        //     std::cout << findValue(i) << ' ';
        // } 

        // std::cout << '\n';
        // std::cout << "active\n";
        // for (int i = 1 ; i <= m ; ++i)
        // {
        //     std::cout << isActive[i] << ' ';
        // }

        // std::cout << '\n';
        // std::cout << "next\n";
        // for (int i = 1 ; i <= m ; ++i)
        // {
        //     std::cout << isNext[i] << ' ';
        // }

        // std::cout << '\n';
    }

    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

dishes.cpp: In function 'void fix(long long int)':
dishes.cpp:123:11: warning: unused variable 'prevVal' [-Wunused-variable]
  123 |     llong prevVal = findValue(col);
      |           ^~~~~~~
dishes.cpp:130:9: warning: variable 'nextVal' set but not used [-Wunused-but-set-variable]
  130 |     int nextVal = 0;
      |         ^~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7761 ms 39532 KB Output is correct
2 Execution timed out 10023 ms 45288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 13144 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12888 KB Output is correct
12 Correct 2 ms 12888 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 2 ms 13076 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 13144 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12888 KB Output is correct
12 Correct 2 ms 12888 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 2 ms 13076 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 29 ms 13072 KB Output is correct
20 Correct 13 ms 12940 KB Output is correct
21 Correct 102 ms 13308 KB Output is correct
22 Correct 29 ms 12888 KB Output is correct
23 Correct 29 ms 12892 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 13144 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12888 KB Output is correct
12 Correct 2 ms 12888 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 2 ms 13076 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 29 ms 13072 KB Output is correct
20 Correct 13 ms 12940 KB Output is correct
21 Correct 102 ms 13308 KB Output is correct
22 Correct 29 ms 12888 KB Output is correct
23 Correct 29 ms 12892 KB Output is correct
24 Correct 174 ms 38132 KB Output is correct
25 Correct 9277 ms 48672 KB Output is correct
26 Execution timed out 10017 ms 42992 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 13144 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12888 KB Output is correct
12 Correct 2 ms 12888 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 2 ms 13076 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 29 ms 13072 KB Output is correct
20 Correct 13 ms 12940 KB Output is correct
21 Correct 102 ms 13308 KB Output is correct
22 Correct 29 ms 12888 KB Output is correct
23 Correct 29 ms 12892 KB Output is correct
24 Correct 174 ms 38132 KB Output is correct
25 Correct 9277 ms 48672 KB Output is correct
26 Execution timed out 10017 ms 42992 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 13144 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12888 KB Output is correct
12 Correct 2 ms 12888 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 2 ms 12888 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 2 ms 13076 KB Output is correct
17 Correct 3 ms 12892 KB Output is correct
18 Correct 4 ms 12892 KB Output is correct
19 Correct 29 ms 13072 KB Output is correct
20 Correct 13 ms 12940 KB Output is correct
21 Correct 102 ms 13308 KB Output is correct
22 Correct 29 ms 12888 KB Output is correct
23 Correct 29 ms 12892 KB Output is correct
24 Correct 174 ms 38132 KB Output is correct
25 Correct 9277 ms 48672 KB Output is correct
26 Execution timed out 10017 ms 42992 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7761 ms 39532 KB Output is correct
2 Execution timed out 10023 ms 45288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7761 ms 39532 KB Output is correct
2 Execution timed out 10023 ms 45288 KB Time limit exceeded
3 Halted 0 ms 0 KB -