oj.uz

Submission #927734

# Submission time Handle Problem Language Result Execution time Memory
927734 2024-02-15T09:34:19 Z boris_mihov Two Dishes (JOI19_dishes) C++17
10 / 100
 10000 ms 49876 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);
    if (col > 1 && fenwickNext.query(col - 1) < col - 1)
    {
        // fix(col - 1);
        int cntZeroesToNow = col - 1 - fenwickNext.query(col - 1);
        int pos = fenwickNext.findKthZero(cntZeroesToNow);
        llong nextVal = findValue(pos + 1) + fenwickActive.query(pos) - fenwickActive.query(pos - 1);

        if (nextVal > dp[pos]) fix(pos);
        // 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 8106 ms 39812 KB Output is correct
2 Execution timed out 10081 ms 38588 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 12892 KB Output is correct
4 Correct 4 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 3 ms 13144 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12964 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 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 4 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 3 ms 13144 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12964 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 5 ms 12892 KB Output is correct
18 Correct 6 ms 12892 KB Output is correct
19 Correct 7 ms 12892 KB Output is correct
20 Correct 7 ms 12892 KB Output is correct
21 Correct 8 ms 12888 KB Output is correct
22 Correct 7 ms 12892 KB Output is correct
23 Correct 8 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 12892 KB Output is correct
4 Correct 4 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 3 ms 13144 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12964 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 5 ms 12892 KB Output is correct
18 Correct 6 ms 12892 KB Output is correct
19 Correct 7 ms 12892 KB Output is correct
20 Correct 7 ms 12892 KB Output is correct
21 Correct 8 ms 12888 KB Output is correct
22 Correct 7 ms 12892 KB Output is correct
23 Correct 8 ms 12892 KB Output is correct
24 Correct 210 ms 38308 KB Output is correct
25 Correct 10000 ms 38220 KB Output is correct
26 Correct 9319 ms 37984 KB Output is correct
27 Correct 9325 ms 49876 KB Output is correct
28 Execution timed out 10018 ms 47700 KB Time limit exceeded
29 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 12892 KB Output is correct
4 Correct 4 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 3 ms 13144 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12964 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 5 ms 12892 KB Output is correct
18 Correct 6 ms 12892 KB Output is correct
19 Correct 7 ms 12892 KB Output is correct
20 Correct 7 ms 12892 KB Output is correct
21 Correct 8 ms 12888 KB Output is correct
22 Correct 7 ms 12892 KB Output is correct
23 Correct 8 ms 12892 KB Output is correct
24 Correct 210 ms 38308 KB Output is correct
25 Correct 10000 ms 38220 KB Output is correct
26 Correct 9319 ms 37984 KB Output is correct
27 Correct 9325 ms 49876 KB Output is correct
28 Execution timed out 10018 ms 47700 KB Time limit exceeded
29 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 12892 KB Output is correct
4 Correct 4 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 3 ms 13144 KB Output is correct
8 Correct 2 ms 12888 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12964 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 5 ms 12892 KB Output is correct
18 Correct 6 ms 12892 KB Output is correct
19 Correct 7 ms 12892 KB Output is correct
20 Correct 7 ms 12892 KB Output is correct
21 Correct 8 ms 12888 KB Output is correct
22 Correct 7 ms 12892 KB Output is correct
23 Correct 8 ms 12892 KB Output is correct
24 Correct 210 ms 38308 KB Output is correct
25 Correct 10000 ms 38220 KB Output is correct
26 Correct 9319 ms 37984 KB Output is correct
27 Correct 9325 ms 49876 KB Output is correct
28 Execution timed out 10018 ms 47700 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8106 ms 39812 KB Output is correct
2 Execution timed out 10081 ms 38588 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8106 ms 39812 KB Output is correct
2 Execution timed out 10081 ms 38588 KB Time limit exceeded
3 Halted 0 ms 0 KB -