#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 3;
const int inf = 1e16 + 2;
int it[N << 2], lazy[N << 2], sA[N], sB[N] ,s[N], t[N], p[N], q[N], ass[N << 2];
vector<pair<int, int> > pts[N];
void init(int idx, int l, int r){
it[idx] = -inf;
ass[idx] = -inf;
if(l == r){
return;
}
int mid = (l + r) >> 1;
init(idx << 1, l, mid);
init(idx << 1 | 1, mid + 1, r);
}
void push(int idx, int l, int r){
if(l == r){
ass[idx] = -inf;
lazy[idx] = 0;
return;
}
ass[idx << 1] = max(ass[idx << 1] + lazy[idx], ass[idx]);
ass[idx << 1 | 1] = max(ass[idx << 1 | 1] + lazy[idx], ass[idx]);
it[idx << 1] = max(it[idx << 1] + lazy[idx], ass[idx]);
it[idx << 1 | 1] = max(it[idx << 1 | 1] + lazy[idx], ass[idx]);
lazy[idx << 1] += lazy[idx];
lazy[idx << 1 | 1] += lazy[idx];
lazy[idx] = 0;
ass[idx] = -inf;
}
void add(int idx, int l, int r, int lef, int rig, int val){
if(l > rig || r < lef){
return;
}
if(l >= lef && r <= rig){
it[idx] += val;
lazy[idx] += val;
ass[idx] += val;
return;
}
push(idx, l, r);
//cout << idx << ' ' << l << ' ' << r << ' ' << lef << ' ' << rig << ' ' << val <<endl;
int mid = (l + r) >> 1;
add(idx << 1, l, mid, lef, rig, val);
add(idx << 1 | 1, mid + 1, r, lef, rig, val);
it[idx] = max(it[idx << 1], it[idx << 1 | 1]);
}
void upd(int idx, int l, int r, int lef, int rig, int val){
if(l > rig || r < lef){
return;
}
if(l >= lef && r <= rig){
ass[idx] = val;
it[idx] = max(it[idx], val);
return;
}
push(idx, l, r);
int mid = (l + r) >> 1;
upd(idx << 1, l, mid, lef, rig, val);
upd(idx << 1 | 1, mid + 1, r, lef, rig, val);
it[idx] = max(it[idx << 1], it[idx << 1 | 1]);
}
int getmax(int idx, int l, int r, int lef, int rig){
if(l > rig || r < lef){
return -inf;
}
if(l >= lef && r <= rig){
return it[idx];
}
push(idx, l, r);
int mid = (l + r) >> 1;
return max(getmax(idx << 1, l, mid, lef, rig), getmax(idx << 1 | 1, mid + 1, r, lef, rig));
}
signed main(){
ios :: sync_with_stdio(0);
cin. tie(0);
int n, m, i, j, k, l, sum_val = 0;
cin >> n >> m;
for(i = 1; i <= n; i++){
cin >> j >> s[i] >> p[i];
sA[i] = sA[i - 1] + j;
}
for(i = 1; i <= m; i++){
cin >> j >> t[i] >> q[i];
sB[i] = sB[i - 1] + j;
sum_val += q[i];
}
for(i = 1; i <= n; i++){
j = upper_bound(sB, sB + 1 + m, s[i] - sA[i]) - sB - 1;
if(j >= 0){
pts[i].push_back({j, p[i]});
}
pts[i].push_back({0, 0});
} //true
for(i = 1; i <= m; i++){
j = upper_bound(sA, sA + 1 + n, t[i] - sB[i]) - sA - 1;
if(j < n){
pts[j + 1].push_back({i - 1, -q[i]});
}
} //true, why? consider the point moving which don't really affect the answer.
init(1, 0, m);
upd(1, 0, m, 0, 0, 0);
pts[0].push_back({0, 0});
sort(pts[0].begin(), pts[0].end());
for(i = 0; i <= n; i++){
sort(pts[i + 1].begin(), pts[i + 1].end());
for(j = 0; j < pts[i].size() - 1; j++){
add(1, 0, m, 0, pts[i][j].first, pts[i][j].second);
}
pts[i].push_back({m + 1, 0});
for(j = 0; j < pts[i].size() - 1; j++){
k = getmax(1, 0, m, 0, min(pts[i][j].first, m));
upd(1, 0, m, pts[i][j].first,pts[i][j + 1].first-1, k);
}
}
cout << getmax(1, 0, m, 0, m) + sum_val;
}
Compilation message
dishes.cpp: In function 'int main()':
dishes.cpp:109:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j = 0; j < pts[i].size() - 1; j++){
~~^~~~~~~~~~~~~~~~~~~
dishes.cpp:113:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j = 0; j < pts[i].size() - 1; j++){
~~^~~~~~~~~~~~~~~~~~~
dishes.cpp:79:21: warning: unused variable 'l' [-Wunused-variable]
int n, m, i, j, k, l, sum_val = 0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
799 ms |
64680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
799 ms |
64680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
799 ms |
64680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
