oj.uz

Submission #927727

# Submission time Handle Problem Language Result Execution time Memory
927727 2024-02-15T09:28:15 Z boris_mihov Two Dishes (JOI19_dishes) C++17
10 / 100
 10000 ms 42684 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);
        // 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 Execution timed out 10090 ms 35428 KB Time limit exceeded
2 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 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12888 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 12888 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 3 ms 12940 KB Output is correct
16 Correct 2 ms 12892 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 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12888 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 12888 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 3 ms 12940 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 190 ms 13392 KB Output is correct
18 Correct 5 ms 13148 KB Output is correct
19 Correct 582 ms 13136 KB Output is correct
20 Correct 372 ms 13128 KB Output is correct
21 Correct 272 ms 13140 KB Output is correct
22 Correct 565 ms 13344 KB Output is correct
23 Correct 539 ms 13140 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 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12888 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 12888 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 3 ms 12940 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 190 ms 13392 KB Output is correct
18 Correct 5 ms 13148 KB Output is correct
19 Correct 582 ms 13136 KB Output is correct
20 Correct 372 ms 13128 KB Output is correct
21 Correct 272 ms 13140 KB Output is correct
22 Correct 565 ms 13344 KB Output is correct
23 Correct 539 ms 13140 KB Output is correct
24 Execution timed out 10008 ms 42684 KB Time limit exceeded
25 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 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12888 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 12888 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 3 ms 12940 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 190 ms 13392 KB Output is correct
18 Correct 5 ms 13148 KB Output is correct
19 Correct 582 ms 13136 KB Output is correct
20 Correct 372 ms 13128 KB Output is correct
21 Correct 272 ms 13140 KB Output is correct
22 Correct 565 ms 13344 KB Output is correct
23 Correct 539 ms 13140 KB Output is correct
24 Execution timed out 10008 ms 42684 KB Time limit exceeded
25 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 3 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12888 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 12888 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 2 ms 12892 KB Output is correct
15 Correct 3 ms 12940 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 190 ms 13392 KB Output is correct
18 Correct 5 ms 13148 KB Output is correct
19 Correct 582 ms 13136 KB Output is correct
20 Correct 372 ms 13128 KB Output is correct
21 Correct 272 ms 13140 KB Output is correct
22 Correct 565 ms 13344 KB Output is correct
23 Correct 539 ms 13140 KB Output is correct
24 Execution timed out 10008 ms 42684 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10090 ms 35428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10090 ms 35428 KB Time limit exceeded
2 Halted 0 ms 0 KB -