#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;typedef long double ld;typedef unsigned long long ul;typedef unsigned int ui;typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e18;
const int inf = 2e9;
template<class T>
void pr(T t) {cerr << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cerr << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cerr << endl;}
int n, m;
struct In{
ll ti, lim, cost;
}A[1000100], B[1000100];
ll ans;
vector<pll> ad[1000100];
ll asum[1000100],bsum[1000100];
ll seg[3000100],blazy[3000100]; // 구간 max, +lazy, fix
int alazy[3000100];
void prop(int x, int l, int r){
if(alazy[x]==1&&blazy[x]==0) return ;
if(l!=r){
alazy[x*2]*=alazy[x];
blazy[x*2] = blazy[x*2]*alazy[x]+blazy[x];
alazy[x*2+1]*=alazy[x];
blazy[x*2+1] = blazy[x*2+1]*alazy[x]+blazy[x];
}
seg[x] = seg[x]*alazy[x] + blazy[x];
alazy[x]=1;blazy[x]=0;
return ;
}
void gang(int x, int l, int r,int s, int e, int a, ll b){
prop(x,l,r);
if(r<s||e<l) return ;
if(s<=l&&r<=e){
alazy[x]*=a;
blazy[x] = blazy[x]*a+b;
prop(x,l,r);
return ;
}
gang(x*2, l, (l+r)/2, s, e, a,b);gang(x*2+1, (l+r)/2+1, r,s,e,a,b);
seg[x] = max(seg[x*2], seg[x*2+1]);
}
ll get_val(int x, int l, int r, int i){
prop(x,l,r);
if(l==r) return seg[x];
int m = (l+r)/2;
if(i<=m) return get_val(x*2, l, m,i);
else return get_val(x*2+1, m+1, r, i);
}
int get_left(int x, int l, int r, ll v){
prop(x,l,r);
if(l==r) return l;
if(seg[x*2]>=v) return get_left(x*2, l,(l+r)/2, v);
return get_left(x*2+1, (l+r)/2+1, r, v);
}
int main(){
fastio;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>A[i].ti>>A[i].lim>>A[i].cost;
asum[i]=asum[i-1]+A[i].ti;
}
for(int i=1;i<=m;i++){
cin>>B[i].ti>>B[i].lim>>B[i].cost;
bsum[i]=bsum[i-1]+B[i].ti;
}
for(int i=1;i<=n;i++){
if(asum[i]>A[i].lim) continue;
int j = upper_bound(bsum,bsum+m+1, A[i].lim-asum[i])-bsum-1;
ans+=A[i].cost;
ad[i-1].eb(j+1, -A[i].cost);
}
for(int i=1;i<=m;i++){
if(bsum[i]>B[i].lim) continue;
int j = upper_bound(asum,asum+n+1, B[i].lim-bsum[i])-asum-1;
ad[j].eb(i,B[i].cost);
}
for(int i=1;i<=3000000;i++){
alazy[i]=1;
}
for(int i=0;i<=n;i++){
sort(all(ad[i]), [](pll &a,pll &b){
if(a.fi==b.fi) return a.se<b.se;
return a.fi>b.fi;});
for(auto j:ad[i]){
if(j.se>=0){
gang(1,0,m,j.fi,m,1,j.se);
continue;
}
else{
ll t = get_val(1,0,m,j.fi-1);
if(seg[1]<t-j.se){
gang(1,0,m,j.fi,m,0,t);
continue;
}
int ind = get_left(1,0,m,t-j.se);
if(j.fi<=ind-1) gang(1,0,m,j.fi,ind-1,0,t);
gang(1,0,m,ind,m,1,j.se);
}
}
}
cout<<ans+seg[1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
448 ms |
65656 KB |
Output is correct |
| 2 |
Incorrect |
402 ms |
66804 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
35584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
448 ms |
65656 KB |
Output is correct |
| 2 |
Incorrect |
402 ms |
66804 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
448 ms |
65656 KB |
Output is correct |
| 2 |
Incorrect |
402 ms |
66804 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
