This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 1e6 + 5, inf = 1e17;
int n,m,a[N],b[N],s[N],p[N],q[N],t[N],x[N],y[N],ans;
int maxim[4 * N], lazy[4 * N];
vector <pii> v[N];
int merge(int a, int b) {
return max(a, b);
}
void push(int node, int le, int ri) {
if (le == ri) {
maxim[node] += lazy[node];
lazy[node] = 0;
return ;
}
maxim[2 * node] = max(maxim[2 * node], maxim[node]);
maxim[2 * node + 1] = max(maxim[2 * node + 1], maxim[node]);
maxim[node] += lazy[node];
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
lazy[node] = 0;
}
void build(int node, int le, int ri) {
if (le == ri) {
maxim[node] = 0;
return ;
} else maxim[node] = -inf;
int mid = (le + ri) / 2;
build(2 * node, le, mid);
build(2 * node + 1, mid + 1, ri);
}
void update(int node, int le, int ri, int start, int end, int val) {
push(node, le, ri);
if (le > end || ri < start || start > end) return ;
if (le >= start && ri <= end) {
lazy[node] += val;
push(node, le, ri);
return ;
}
int mid = (le + ri) / 2;
update(2 * node, le, mid, start, end, val);
update(2 * node + 1, mid + 1, ri, start, end, val);
}
void maximize(int node, int le, int ri, int start, int end, int val) {
push(node, le, ri);
if (le > end || ri < start || start > end) return ;
if (le >= start && ri <= end) {
//cout<<node<<" "<<val<<"\n";
maxim[node] = max(maxim[node], val);
push(node, le, ri);
return ;
}
int mid = (le + ri) / 2;
maximize(2 * node, le, mid,start,end,val);
maximize(2 * node + 1, mid + 1, ri, start, end, val);
}
int getans(int node, int le, int ri, int idx) {
push(node, le, ri);
if (le > idx || ri < idx) return -inf;
if (le == ri) {
return maxim[node];
}
int mid = (le + ri) / 2;
return merge(getans(2 * node, le, mid, idx), getans(2 * node + 1, mid + 1, ri, idx));
}
/*
void prnt(int node, int le, int ri) {
// cout<<node<<" "<<le<<" "<<ri<<" "<<maxim[node]<<" "<<lazy[node]<<"\n";
if (le == ri) return ;
int mid = (le + ri) / 2;
prnt(2 * node, le, mid);
prnt(2 * node + 1, mid + 1, ri);
}
*/
main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for (int i = 1; i <= n; i++) {
cin>>a[i]>>s[i]>>p[i];
a[i] += a[i - 1];
}
for (int i = 1; i <= m; i++) {
cin>>b[i]>>t[i]>>q[i];
b[i] += b[i - 1];
}
for (int i = 1; i <= n; i++) {
if (a[i] > s[i]) continue;
x[i] = upper_bound(b, b + m + 1, s[i] - a[i]) - b; // x[i] = minimum index such that pra[i] + prb[idx] > s[i]
v[i].pb({x[i], p[i]});
// cout<<i<<" "<<x[i]<<"\n";
}
build(1, 0, m);
for (int i = 1; i <= m; i++) {
if (b[i] > t[i]) continue;
y[i] = upper_bound(a, a + n + 1, t[i] - b[i]) - a; // y[i] = minimum index such that prb[i] + pra[idx] > t[i];
// cout<<y[i]<<" -- "<<i<<"\n";
ans += q[i];
v[y[i]].pb({i, -q[i]});
}
for (int i = 1; i <= n; i++) {
v[i].pb({0, 0}); v[i].pb({m + 1, 0});
sort(v[i].begin(), v[i].end());
for (pii sth : v[i]) {
int j = sth.f; int cost = sth.s;
update(1, 0, m, 0, j - 1, cost);
}
// prefix maximization
for (pii sth : v[i]) {
int j = sth.f; int cost = sth.s;
int x = getans(1,0,m, j - 1);
maximize(1,0,m,j, m,x);
}
}
int ans1 = -inf;
for (int i = 1; i <= m; i++) {
ans1 = max(ans1, getans(1,0,m, i));
}
cout<<ans + ans1<<"\n";
}
Compilation message (stderr)
dishes.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
84 | main() {
| ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:118:23: warning: unused variable 'cost' [-Wunused-variable]
118 | int j = sth.f; int cost = sth.s;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |