// 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
525 ms |
73592 KB |
Output is correct |
| 2 |
Incorrect |
550 ms |
73004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
49492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
49492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
49492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
49492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
49492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
525 ms |
73592 KB |
Output is correct |
| 2 |
Incorrect |
550 ms |
73004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
525 ms |
73592 KB |
Output is correct |
| 2 |
Incorrect |
550 ms |
73004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
