oj.uz

답안 #938676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938676 2024-03-05T12:17:02 Z danikoynov Two Dishes (JOI19_dishes) C++14
3 / 100
 456 ms 96208 KB 
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e6 + 10;

int n, m;
ll a[maxn], s[maxn], p[maxn];
ll b[maxn], t[maxn], q[maxn];
ll pref[2][maxn];

void input()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> a[i] >> s[i] >> p[i];
    for (int i = 1; i <= m; i ++)
        cin >> b[i] >> t[i] >> q[i];
}

void prefix_sums()
{
    for (int i = 1; i <= n; i ++)
    {
        pref[0][i] = pref[0][i - 1] + a[i];
    }
    for (int i = 1; i <= m; i ++)
    {
        pref[1][i] = pref[1][i - 1] + b[i];
    }
}

ll dp[maxn], temp[maxn];
vector < pair < int, ll > > upd[maxn];
int X[maxn], Y[maxn];
const ll inf = 1e18;

ll tree[4 * maxn];
pair < ll, ll > lazy[4 * maxn]; /// first is addition; second is set
pair < int, int > tag[4 * maxn];

void push_lazy(int root, int left, int right)
{

        if (tag[root].second == 1)
        {
            tree[root] = lazy[root].second;
        }
        if (tag[root].first == 1)
            tree[root] += lazy[root].first;

        if (left != right)
        {
            if (tag[root].second == 1)
            {
                lazy[root * 2] = {0, lazy[root].second};
                lazy[root * 2 + 1] = {0, lazy[root].second};
                tag[root * 2] = {0, 1};
                tag[root * 2 + 1] = {0, 1};
            }
            if (tag[root].first == 1)
            {
                lazy[root * 2].first += lazy[root].first;
                lazy[root * 2 + 1].first += lazy[root].first;
                tag[root * 2].first = 1;
                tag[root * 2 + 1].first = 1;
            }
        }

        lazy[root] = {0, 0};
        tag[root] = {0, 0};

}

void build(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = dp[left];
        return;
    }

    int mid = (left + right) / 2;
    build(root * 2, left, mid);
    build(root * 2 + 1, mid + 1, right);

    tree[root] = min(tree[root * 2], tree[root * 2 + 1]);
}
ll query(int root, int left, int right, int pivot)
{
    push_lazy(root, left, right);
    if (left == right)
        return tree[root];

    int mid = (left + right) / 2;
    if (pivot <= mid)
        return query(root * 2, left, mid, pivot);
    else
        return query(root * 2 + 1, mid + 1, right, pivot);
}
void range_add(int root, int left, int right, int qleft, int qright, ll val)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        lazy[root] = {val, 0};
        tag[root] = {1, 0};
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    range_add(root * 2, left, mid, qleft, qright, val);
    range_add(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = min(tree[root * 2], tree[root * 2 + 1]);

}

void set_range(int root, int left, int right, int qleft, int qright, ll val)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        lazy[root] = {0, val};
        tag[root] = {0, 1};
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    set_range(root * 2, left, mid, qleft, qright, val);
    set_range(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = min(tree[root * 2], tree[root * 2 + 1]);

}

int walk(int root, int left, int right, int qleft, int qright, ll val)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft || tree[root] >= val)
        return qleft - 1;

    if (left == right)
        return left;

        int mid = (left + right) / 2;
    if (left >= qleft && right <= qright)
    {
        if (tree[root * 2 + 1] < val)
            return walk(root * 2 + 1, mid + 1, right, qleft, qright, val);
        return walk(root * 2, left, mid, qleft, qright, val);
    }


    return max(walk(root * 2, left, mid, qleft, qright, val),
               walk(root * 2 + 1, mid + 1, right, qleft, qright, val));
}

void dynamic()
{
    for (int i = 1; i <= n; i ++)
    {
        ll free_time = s[i] - pref[0][i];
        int lf = 0, rf = m;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (pref[1][mf] <= free_time)
                lf = mf + 1;
            else
                rf = mf - 1;
        }
        X[i] = rf;

        /**while(X[i] <= m && pref[1][X[i]] <= free_time)
            X[i] ++;
        X[i] --;*/



        upd[i - 1].push_back({X[i] + 1, - p[i]});
        ///cout << "point " << i - 1 << " " << X[i] + 1 << " " << -p[i] << endl;


    }

    for (int i = 1; i <= m; i ++)
    {
        ll free_time = t[i] - pref[1][i];
        int lf = 0, rf = n;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (pref[0][mf] <= free_time)
                lf = mf + 1;
            else
                rf = mf - 1;
        }
        Y[i] = rf;

        /**while(Y[i] <= n && pref[0][Y[i]] <= free_time)
            Y[i] ++;
        Y[i] --;*/

        if (Y[i] >= 0)
        {
            upd[Y[i]].push_back({i, q[i]});

            //cout << "point " << Y[i] << " " << i << " " << q[i] << endl;
        }
    }

    for (int j = 0; j <= m; j ++)
        dp[j] = 0;
    for (pair < int, ll > cur : upd[0])
        for (int d = cur.first; d <= m; d ++)
        dp[d] += cur.second;

    for (int i = 1; i <= m; i ++)
        dp[i] = max(dp[i], dp[i - 1]);

    build(1, 0, m);

    for (int i = 1; i <= n; i ++)
    {
        sort(upd[i].begin(), upd[i].end());

    /**cout << "--------------" << endl;
    for (int j = 0; j <= m; j ++)
    {
        cout << dp[j] << " " << query(1, 0, m, j) << endl;
    }*/
        ll sum = 0;
        for (int j = 0; j < upd[i].size(); j ++)
        {
            int cur = upd[i][j].first;
            int nxt = m + 1;
            if (j + 1 < upd[i].size())
                nxt = upd[i][j + 1].first;

            sum += upd[i][j].second;
            if (upd[i][j].first == 0 || i == n)
            {
                range_add(1, 0, m, cur, nxt - 1, sum);
                //for (int d = cur; d < nxt; d ++)
                  //  dp[d] += sum;
            }
            else
            {
                ll bef = query(1, 0, m, upd[i][j].first - 1);
                int last = walk(1, 0, m, cur, nxt - 1, bef - sum);
                /**int lf = cur, rf = nxt - 1;
                while(lf <= rf)
                {
                    int mf=  (lf + rf) / 2;
                    if (query(1, 0, m, mf) + sum < bef)
                        lf = mf + 1;
                    else
                        rf = mf - 1;
                }
                last = lf - 1;*/
                /**for (int d = cur; d < nxt; d ++)
                {
                    if (query(1, 0, m, d) + sum < bef)
                        last = d;
                }*/

                set_range(1, 0, m, cur, last, bef);
                range_add(1, 0, m, last + 1, nxt - 1, sum);
                /**for (int d = cur; d <= last; d ++)
                    dp[d] = bef;
                for (int d = last + 1; d < nxt; d ++)
                    dp[d] += sum;*/

            }
        }
        /*for (pair < int, ll > cur : upd[i])
        {
            sum += cur.second;

            ll var = dp[cur.first] + sum;

            //cout << "update point " << cur.first << " " << cur.second << endl;

            for (int d = cur.first; d <= m; d ++)
            {
                temp[d] += cur.second;
            }
        }
        for (int j = 0; j <= m; j ++)
        {
            ///best = max(best, dp[j]);
            dp[j] += temp[j];
        }

        if (i != n)
        {
            for (int j = 1; j <= m; j ++)
                dp[j] = max(dp[j - 1], dp[j]);
        }*/

        /**cout << "state " << i << endl;
        for (int j = 0; j <= m; j ++)
            cout << dp[j] << " ";
        cout << endl;*/
    }

    ll res = 0;
    for (int i = 1; i <= n; i ++)
        res += p[i];

    res = res + query(1, 0, m, m);
    cout << res << endl;




    /**for (int i = 0; i <= n; i ++)
    {
        for (int j = 0; j <= m; j ++)
        {
            if (i > 0)
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + (pref[0][i] + pref[1][j] <= s[i]));
            }
            if (j > 0)
            {
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + (pref[0][i] + pref[1][j] <= t[j]));
            }

            ///cout << "state " << i << "  " << j << " " << dp[i][j] << endl;
        }
    }

    cout << dp[n][m] << endl;*/



}
void solve()
{
    input();
    prefix_sums();
    dynamic();
}

int main()
{
    speed();
    solve();
    return 0;
}
/**
9 12
414814218 278771326 1
142790158 568604393 1
155567225 14012701 1
627555390 1224920860 1
677068511 5243031298 1
580933994 8598159379 1
819258172 1432469030 1
340548310 999347990 1
432162069 4373255579 1
99824657 11080715 1
756309567 9502204999 1
929699364 2343419815 1
376204577 6097684636 1
399553538 2306014840 1
824786328 4994974413 1
536419761 3247725215 1
953903194 10674273733 1
787043482 3936134684 1
105275489 567691865 1
861537554 117255456 1
434345770 2420939138 1

*/

Compilation message

dishes.cpp: In function 'int walk(int, int, int, int, int, ll)':
dishes.cpp:160:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  160 |     if (left == right)
      |     ^~
dishes.cpp:163:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  163 |         int mid = (left + right) / 2;
      |         ^~~
dishes.cpp: In function 'void dynamic()':
dishes.cpp:251:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |         for (int j = 0; j < upd[i].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~
dishes.cpp:255:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  255 |             if (j + 1 < upd[i].size())
      |                 ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 405 ms 93788 KB Output is correct
2 Correct 456 ms 96208 KB Output is correct
3 Correct 190 ms 95668 KB Output is correct
4 Correct 292 ms 90124 KB Output is correct
5 Correct 8 ms 49500 KB Output is correct
6 Correct 389 ms 95896 KB Output is correct
7 Correct 105 ms 76488 KB Output is correct
8 Correct 85 ms 66312 KB Output is correct
9 Correct 198 ms 95096 KB Output is correct
10 Incorrect 434 ms 95076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 49496 KB Output is correct
2 Correct 9 ms 49756 KB Output is correct
3 Correct 9 ms 49616 KB Output is correct
4 Correct 8 ms 49500 KB Output is correct
5 Correct 9 ms 49724 KB Output is correct
6 Correct 9 ms 49500 KB Output is correct
7 Correct 8 ms 49500 KB Output is correct
8 Correct 8 ms 49500 KB Output is correct
9 Correct 8 ms 49684 KB Output is correct
10 Correct 9 ms 49500 KB Output is correct
11 Correct 9 ms 49860 KB Output is correct
12 Correct 8 ms 49500 KB Output is correct
13 Correct 9 ms 49620 KB Output is correct
14 Correct 9 ms 49496 KB Output is correct
15 Correct 9 ms 49496 KB Output is correct
16 Correct 9 ms 49756 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 49496 KB Output is correct
2 Correct 9 ms 49756 KB Output is correct
3 Correct 9 ms 49616 KB Output is correct
4 Correct 8 ms 49500 KB Output is correct
5 Correct 9 ms 49724 KB Output is correct
6 Correct 9 ms 49500 KB Output is correct
7 Correct 8 ms 49500 KB Output is correct
8 Correct 8 ms 49500 KB Output is correct
9 Correct 8 ms 49684 KB Output is correct
10 Correct 9 ms 49500 KB Output is correct
11 Correct 9 ms 49860 KB Output is correct
12 Correct 8 ms 49500 KB Output is correct
13 Correct 9 ms 49620 KB Output is correct
14 Correct 9 ms 49496 KB Output is correct
15 Correct 9 ms 49496 KB Output is correct
16 Correct 9 ms 49756 KB Output is correct
17 Correct 11 ms 49752 KB Output is correct
18 Correct 10 ms 49884 KB Output is correct
19 Incorrect 13 ms 49756 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 49496 KB Output is correct
2 Correct 9 ms 49756 KB Output is correct
3 Correct 9 ms 49616 KB Output is correct
4 Correct 8 ms 49500 KB Output is correct
5 Correct 9 ms 49724 KB Output is correct
6 Correct 9 ms 49500 KB Output is correct
7 Correct 8 ms 49500 KB Output is correct
8 Correct 8 ms 49500 KB Output is correct
9 Correct 8 ms 49684 KB Output is correct
10 Correct 9 ms 49500 KB Output is correct
11 Correct 9 ms 49860 KB Output is correct
12 Correct 8 ms 49500 KB Output is correct
13 Correct 9 ms 49620 KB Output is correct
14 Correct 9 ms 49496 KB Output is correct
15 Correct 9 ms 49496 KB Output is correct
16 Correct 9 ms 49756 KB Output is correct
17 Correct 11 ms 49752 KB Output is correct
18 Correct 10 ms 49884 KB Output is correct
19 Incorrect 13 ms 49756 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 49496 KB Output is correct
2 Correct 9 ms 49756 KB Output is correct
3 Correct 9 ms 49616 KB Output is correct
4 Correct 8 ms 49500 KB Output is correct
5 Correct 9 ms 49724 KB Output is correct
6 Correct 9 ms 49500 KB Output is correct
7 Correct 8 ms 49500 KB Output is correct
8 Correct 8 ms 49500 KB Output is correct
9 Correct 8 ms 49684 KB Output is correct
10 Correct 9 ms 49500 KB Output is correct
11 Correct 9 ms 49860 KB Output is correct
12 Correct 8 ms 49500 KB Output is correct
13 Correct 9 ms 49620 KB Output is correct
14 Correct 9 ms 49496 KB Output is correct
15 Correct 9 ms 49496 KB Output is correct
16 Correct 9 ms 49756 KB Output is correct
17 Correct 11 ms 49752 KB Output is correct
18 Correct 10 ms 49884 KB Output is correct
19 Incorrect 13 ms 49756 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 49496 KB Output is correct
2 Correct 9 ms 49756 KB Output is correct
3 Correct 9 ms 49616 KB Output is correct
4 Correct 8 ms 49500 KB Output is correct
5 Correct 9 ms 49724 KB Output is correct
6 Correct 9 ms 49500 KB Output is correct
7 Correct 8 ms 49500 KB Output is correct
8 Correct 8 ms 49500 KB Output is correct
9 Correct 8 ms 49684 KB Output is correct
10 Correct 9 ms 49500 KB Output is correct
11 Correct 9 ms 49860 KB Output is correct
12 Correct 8 ms 49500 KB Output is correct
13 Correct 9 ms 49620 KB Output is correct
14 Correct 9 ms 49496 KB Output is correct
15 Correct 9 ms 49496 KB Output is correct
16 Correct 9 ms 49756 KB Output is correct
17 Correct 11 ms 49752 KB Output is correct
18 Correct 10 ms 49884 KB Output is correct
19 Incorrect 13 ms 49756 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 405 ms 93788 KB Output is correct
2 Correct 456 ms 96208 KB Output is correct
3 Correct 190 ms 95668 KB Output is correct
4 Correct 292 ms 90124 KB Output is correct
5 Correct 8 ms 49500 KB Output is correct
6 Correct 389 ms 95896 KB Output is correct
7 Correct 105 ms 76488 KB Output is correct
8 Correct 85 ms 66312 KB Output is correct
9 Correct 198 ms 95096 KB Output is correct
10 Incorrect 434 ms 95076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 405 ms 93788 KB Output is correct
2 Correct 456 ms 96208 KB Output is correct
3 Correct 190 ms 95668 KB Output is correct
4 Correct 292 ms 90124 KB Output is correct
5 Correct 8 ms 49500 KB Output is correct
6 Correct 389 ms 95896 KB Output is correct
7 Correct 105 ms 76488 KB Output is correct
8 Correct 85 ms 66312 KB Output is correct
9 Correct 198 ms 95096 KB Output is correct
10 Incorrect 434 ms 95076 KB Output isn't correct
11 Halted 0 ms 0 KB -