#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
const int inf=1e18;
struct ST{
vector<pair<int,int> > st;
void init(int x){
st.resize(4*x);
}
void upd(int v,int x){
st[v].fs+=x;
st[v].sc+=x;
}
void pudo(int v){
upd(2*v+1,st[v].sc);
upd(2*v+2,st[v].sc);
st[v].sc=0;
}
void pull(int v){
st[v].fs=max(st[2*v+1].fs,st[2*v+2].fs);
}
void update(int v,int L,int R,int l,int r,int k){
if(L==l && r==R){
upd(v,k);
return;
}
int m=(L+R)/2;
pudo(v);
if(r<=m){
update(2*v+1,L,m,l,r,k);
}
else if(l>m){
update(2*v+2,m+1,R,l,r,k);
}
else{
update(2*v+1,L,m,l,m,k);
update(2*v+2,m+1,R,m+1,r,k);
}
pull(v);
}
int query(int v,int L,int R,int l,int r){
if(L==l && r==R){
return st[v].fs;
}
pudo(v);
int m=(L+R)/2;
if(r<=m){
return query(2*v+1,L,m,l,r);
}
else if(l>m){
return query(2*v+2,m+1,R,l,r);
}
else{
return max(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
}
}
}st;
struct BIT{
int n;
vector<int> bt;
void init(int x){
n=x;
bt.resize(n+1);
}
void update(int x,int y){
for(;x>0;x-=(x&-x)){
bt[x]+=y;
}
}
int query(int x){
int ans=0;
for(;x<=n;x+=(x&-x)){
ans+=bt[x];
}
return ans;
}
}bt,bt2;
bool cmp(pair<int,int> a,pair<int,int> b){
return a.sc!=b.sc?a.sc<b.sc:a.fs<b.fs;
}
signed main(){
AquA;
freopen("07-10.txt","r",stdin);
freopen("ans.txt","w",stdout);
int n,m;
cin >> n >> m;
vector<int> a(n+1),b(m+1),s(n+1),t(m+1),p(n+1),q(m+1);
for(int i=1;i<=n;i++){
cin >> a[i] >> s[i] >> p[i];
a[i]+=a[i-1];
}
for(int j=1;j<=m;j++){
cin >> b[j] >> t[j] >> q[j];
b[j]+=b[j-1];
}
vector<pair<int,int> > gg;
vector<int> oka(n+1),okb(m+2);
vector<pair<int,int> > to;
vector<int> vis(n+2);
for(int i=1;i<=n;i++){
oka[i]=upper_bound(b.begin(),b.end(),s[i]-a[i])-b.begin()-1;
if(oka[i]<0){
continue;
}
to.push_back({oka[i],i});
}
for(int i=1;i<=m;i++){
okb[i]=upper_bound(a.begin(),a.end(),t[i]-b[i])-a.begin()-1;
if(okb[i]<0){
q[i]=0;
continue;
}
if(okb[i]>=n){
}
else{
to.push_back({i-1,okb[i]+1});
}
}
to.push_back({m,n+1});
sort(to.begin(),to.end(),[&](pair<int,int> a,pair<int,int> b){
return a.fs!=b.fs?a.fs<b.fs:a.sc>b.sc;
});
to.erase(unique(to.begin(),to.end()),to.end());
gg=to;
sort(gg.begin(),gg.end(),cmp);
n=gg.size();
vector<int> newp(n+1);
for(auto &h:to){
if(h.fs<0){
continue;
}
int flag=-1;
if(!vis[h.sc] && h.fs==oka[h.sc]){
vis[h.sc]=1;
flag=h.sc;
}
h.sc=lower_bound(gg.begin(),gg.end(),h,cmp)-gg.begin()+1;
if(flag>=0){
newp[h.sc]=p[flag];
}
}
st.init(n+1);
bt.init(n);
bt2.init(n);
st.update(0,0,n,1,n,-inf);
for(int i=1;i<=n;i++){
st.update(0,0,n,0,i-1,newp[i]);
bt.update(i,newp[i]);
}
int l=0;
vector<int> dp(n+1);
for(int i=1;i<=m;i++){
if(okb[i]>=0){
okb[i]=lower_bound(gg.begin(),gg.end(),pair<int,int>(-inf,okb[i]+1),cmp)-gg.begin();
}
}
for(int i=0;i<=m;i++){
if(i>0 && i<=m && okb[i]>=0){
st.update(0,0,n,0,okb[i],q[i]);
bt2.update(okb[i],q[i]);
}
while(l<(int)to.size() && to[l].fs==i){
int x=to[l].sc;
dp[x]=st.query(0,0,n,0,x-1)-bt.query(x+1);
st.update(0,0,n,x,x,dp[x]+inf-bt2.query(x));
st.update(0,0,n,0,x-1,-newp[x]);
bt.update(x,-newp[x]);
l++;
}
}
cout << dp[n] << "\n";
return 0;
}
Compilation message
dishes.cpp: In function 'int main()':
dishes.cpp:92:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | freopen("07-10.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:93:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | freopen("ans.txt","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
