| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1094213 |
2024-09-29T02:59:17 Z |
8pete8 |
Two Dishes (JOI19_dishes) |
C++17 |
|
145 ms |
31940 KB |
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<ll,ll>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define ll long long
#define double long double
using namespace std;
const ll mod=998244353,mxn=1e6+5,inf=1e16,minf=-1e16,lg=30;
//#undef int
int n,k,m,q;
void setIO(string name){
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
pair<ll,pii> v1[mxn+10],v2[mxn+10];
//time,before,point
struct seg{
ll v[4*mxn+10],lazy1[4*mxn+10],lazy2[4*mxn+10];
void init(){for(int i=0;i<=4*(n+1);i++)lazy2[i]=minf,v[i]=0;}
void push(int l,int r,int pos){
v[pos]=max(v[pos]+lazy1[pos],lazy2[pos]);
if(l!=r){
if(lazy2[pos*2]!=minf)lazy2[pos*2]+=lazy1[pos];
if(lazy2[pos*2+1]!=minf)lazy2[pos*2+1]+=lazy1[pos];
lazy1[pos*2+1]+=lazy1[pos];
lazy1[pos*2]+=lazy1[pos];
lazy2[pos*2]=max(lazy2[pos*2],lazy2[pos]);
lazy2[pos*2+1]=max(lazy2[pos*2+1],lazy2[pos]);
}
//22 oct 17.50
lazy2[pos]=minf;
lazy1[pos]=0;
}
void updateadd(int l,int r,int ql,int qr,ll val,int pos){
push(l,r,pos);
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr){
lazy1[pos]+=val;
push(l,r,pos);
return;
}
int mid=l+(r-l)/2;
updateadd(l,mid,ql,qr,val,pos*2);
updateadd(mid+1,r,ql,qr,val,pos*2+1);
v[pos]=max(v[pos*2],v[pos*2+1]);
}
void updateset(int l,int r,int ql,int qr,ll val,int pos){
push(l,r,pos);
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr){
lazy2[pos]=max(lazy2[pos],val);
push(l,r,pos);
return;
}
int mid=l+(r-l)/2;
updateset(l,mid,ql,qr,val,pos*2);
updateset(mid+1,r,ql,qr,val,pos*2+1);
v[pos]=max(v[pos*2],v[pos*2+1]);
}
int qry(int l,int r,int qpos,int pos){
push(l,r,pos);
if(l==r)return v[pos];
int mid=l+(r-l)/2;
if(qpos<=mid)return qry(l,mid,qpos,pos*2);
return qry(mid+1,r,qpos,pos*2+1);
}
}t;
int getbound(int x,ll add){
int l=0,r=n,pos=-1;
while(l<=r){
int mid=l+(r-l)/2;
if(v1[mid].f+add<=x)l=mid+1,pos=max(pos,mid);
else r=mid-1;
}
return pos;
}
int32_t main(){
fastio
//n^2 can use lazy seg to op
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v1[i].f>>v1[i].s.f>>v1[i].s.s;
v1[i].f+=v1[i-1].f;
}
for(int i=1;i<=m;i++){
cin>>v2[i].f>>v2[i].s.f>>v2[i].s.s;
v2[i].f+=v2[i-1].f;
}
ll ans1=0;
vector<pii>gap;
for(int i=1;i<=n;i++){
if(v1[i].f<=v1[i].s.f){
gap.pb({v1[i].s.f-v1[i].f,i});
ans1+=v1[i].s.s;
}
}
t.init();
sort(all(gap));
ll cur=0,bruh,where;
vector<int>cut;//
for(int j=1;j<=m;j++){
while(cur<gap.size()&&gap[cur].f<v2[j].f){
t.updateadd(0,n,0,gap[cur].s-1,-v1[gap[cur].s].s.s,1);
if(v1[gap[cur].s].s.s<0)cut.pb(gap[cur].s-1);
cur++;
}
int x=getbound(v2[j].s.f,v2[j].f);
if(x!=-1){
cut.pb(x);
t.updateadd(0,n,0,x,v2[j].s.s,1);
if(v2[j].s.s>0)cut.pb(x);
}
for(auto i:cut){
bruh=t.qry(0,n,i,1);
t.updateset(0,n,i+1,n,bruh,1);
}
cut.clear();
}
t.push(0,n,1);
cout<<ans1+t.v[1]<<'\n';
}
/*
*/
Compilation message
dishes.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize ("03,unroll-lopps")
| ^
dishes.cpp:39:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
39 | void setIO(string name){
| ^
dishes.cpp:48:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
48 | void init(){for(int i=0;i<=4*(n+1);i++)lazy2[i]=minf,v[i]=0;}
| ^
dishes.cpp:49:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
49 | void push(int l,int r,int pos){
| ^
dishes.cpp:63:60: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
63 | void updateadd(int l,int r,int ql,int qr,ll val,int pos){
| ^
dishes.cpp:76:60: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
76 | void updateset(int l,int r,int ql,int qr,ll val,int pos){
| ^
dishes.cpp:89:41: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
89 | int qry(int l,int r,int qpos,int pos){
| ^
dishes.cpp:97:26: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
97 | int getbound(int x,ll add){
| ^
dishes.cpp:106:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
106 | int32_t main(){
| ^
dishes.cpp: In function 'int32_t main()':
dishes.cpp:131:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | while(cur<gap.size()&&gap[cur].f<v2[j].f){
| ~~~^~~~~~~~~~~
dishes.cpp:128:16: warning: unused variable 'where' [-Wunused-variable]
128 | ll cur=0,bruh,where;
| ^~~~~
dishes.cpp: In function 'void setIO(std::string)':
dishes.cpp:41:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:42:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
31940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
31940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
145 ms |
31940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
