Submission #697145

#	Time	Username	Problem	Language	Result	Execution time	Memory
697145		elkernos	Two Dishes (JOI19_dishes)	C++17	0 / 100	550 ms	73592 KiB

dishes

// while (clock()<=69*CLOCKS_PER_SEC)
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
// #pragma GCC target ("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                    \
    sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
    {
sim > struct rge {
    c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
    ~debug()
    {
        cerr << endl;
    }
    eni(!=) cerr << boolalpha << i;
    ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
    ris << "" << d.first << " --> " << d.second << "";
}
sim dor(rge<c> d)
{
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
    sim dor(const c &)
    {
        ris;
    }
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#ifdef XOX
#warning Times may differ!!!
#endif

#define endl '\n'
#define pb emplace_back
#define vt vector
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define int long long

const int oo = 1e18 + 123;
struct Node {
    int maxi;
    int lazy_sum, lazy_max;
};
#define md (l + r) / 2
#define lc 2 * v
#define rc 2 * v + 1

int m;
vector<Node> tree(1 << 21);

void pchaj(int v, int l, int r)
{
    auto &me = tree[v];
    me.maxi += me.lazy_sum;
    me.maxi = max(me.maxi, me.lazy_max);
    if (l != r) {
        auto &to_left = tree[lc];
        to_left.lazy_max = max(to_left.lazy_max + me.lazy_sum, me.lazy_max);
        to_left.lazy_sum += me.lazy_sum;
        auto &to_right = tree[rc];
        to_right.lazy_max = max(to_right.lazy_max + me.lazy_sum, me.lazy_max);
        to_right.lazy_sum += me.lazy_sum;
    }
    me.lazy_max = -oo, me.lazy_sum = 0;
}

int pyt(int ql, int qr, int l = 0, int r = m, int v = 1)
{
    pchaj(v, l, r);
    if (ql > r || qr < l) return -oo;
    if (ql <= l && qr >= r) return tree[v].maxi;
    return max(pyt(ql, qr, l, md, lc),
               pyt(ql, qr, md + 1, r, rc));
}

void pisz(int ql, int qr, int sum, int maxuj, int l = 0, int r = m, int v = 1)
{
    pchaj(v, l, r);
    if (ql > r || qr < l) return;
    auto &me = tree[v];
    if (ql <= l && qr >= r) {
        me.lazy_max = max(me.lazy_max, maxuj);
        me.lazy_max += sum;
        me.lazy_sum += sum;
        pchaj(v, l, r);
        return;
    }
    pisz(ql, qr, sum, maxuj, l, md, lc);
    pisz(ql, qr, sum, maxuj, md + 1, r, rc);
    assert(me.lazy_max == -oo && me.lazy_sum == 0);
    me.maxi = max(tree[lc].maxi, tree[rc].maxi);
}

#undef lc
#undef rc
#undef md

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n >> m;
    vector<int> a(n + 1), s(n + 1), p(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> s[i] >> p[i];
        a[i] += a[i - 1];
    }
    vector<int> b(m + 1), t(m + 1), q(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> b[i] >> t[i] >> q[i];
        b[i] += b[i - 1];
    }
    vector<vector<pair<int, int>>> events(n + 1);
    int add = 0;
    for (int i = 1; i <= n; i++) {
        int where = upper_bound(all(b), s[i] - a[i]) - b.begin();
        if (where >= 1) {
            if (where == m + 1) {
                add += p[i];
                debug() << "zawsze" imie(p[i]);
                continue;
            }
            events[i].push_back({where - 1, p[i]});
            debug() << "od a: " << i << ", " << where - 1 << ", " << p[i];
        }
    }
    for (int i = 1; i <= m; i++) {
        int where = upper_bound(all(a), t[i] - b[i]) - a.begin();
        if (where >= 1) {
            if (where == n + 1) {
                add += q[i];
                debug() << "zawsze" imie(q[i]);
                continue;
            }
            add += q[i];
            q[i] *= -1;
            events[where].push_back({i - 1, q[i]});
            debug() << "od b: " << where << ", " << i - 1 << ", " << q[i];
        }
    }
    for (int rep = 1; rep <= n; rep++) {
        sort(events[rep].begin(), events[rep].end(), [&](auto &i, auto &j) { // need
            return i.first > j.first;
        });
        debug() << imie(events[rep]);
        for (auto [from, inc] : events[rep]) {
            // dodaj na [from, n] inc
            pisz(0, from, inc, -oo);
            int his_dp = pyt(0, from);
            debug() << imie(his_dp);
            pisz(from + 1, m, 0, his_dp);
        }
    }
    // add + wartosc w n
    cout << add + tree[1].maxi << endl;
}

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