| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1094064 |
2024-09-28T11:22:38 Z |
8pete8 |
Two Dishes (JOI19_dishes) |
C++17 |
|
247 ms |
41152 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<int,int>
#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 int long long
#define double long double
using namespace std;
const int mod=998244353,mxn=1e6+5,inf=1e18,minf=-1e18,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<int,pii> v1[mxn+10],v2[mxn+10];
//time,before,point
int gap[mxn+10],dp[mxn+10],suf[mxn+10];
struct seg{
int 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]=inf,v[i]=minf;}
void build(int l,int r,int pos){
int mid=l+(r-l)/2;
v[pos]=0;
if(l==r)return;
build(l,mid,pos*2);
build(mid+1,r,pos*2+1);
}
void push(int l,int r,int pos){
if(lazy2[pos]!=inf)v[pos]=lazy2[pos];
v[pos]+=lazy1[pos];
if(l!=r){
if(lazy2[pos]!=inf)lazy1[pos*2+1]=0,lazy1[pos*2]=0;
lazy1[pos*2+1]+=lazy1[pos];
lazy1[pos*2]+=lazy1[pos];
if(lazy2[pos]!=inf){
lazy2[pos*2+1]=lazy2[pos];
lazy2[pos*2]=lazy2[pos];
}
}
lazy2[pos]=inf;
lazy1[pos]=0;
}
void updateadd(int l,int r,int ql,int qr,int 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,int val,int pos){
push(l,r,pos);
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr){
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);
}
int search(int l,int r,int ql,int qr,int val,int pos){
//search pos where i<x
push(l,r,pos);
int mid=l+(r-l)/2;
if(l>qr||r<ql)return -1;
if(l>=ql&&r<=qr){
if(l==r){
if(v[pos]<val)return r;
return -1;
}
if(v[pos]<val)return r;
else{
push(l,mid,pos*2);
push(mid+1,r,pos*2+1);
if(v[pos*2]<val)return max(mid,search(mid+1,r,ql,qr,val,pos*2+1));
else return search(l,mid,ql,qr,val,pos*2);
}
}
return max(search(l,mid,ql,qr,val,pos*2),search(mid+1,r,ql,qr,val,pos*2+1));
}
}t;
int getbound(int x,int 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;
}
int 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();
t.build(0,n,1);
sort(all(gap));
int cur=0,bruh,where;
t.updateadd(0,n,1,n,minf,1);
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){
bruh=t.qry(0,n,gap[cur].s-1,1);
where=t.search(0,n,gap[cur].s,n,bruh,1);
if(where!=-1)t.updateset(0,n,gap[cur].s,where,bruh,1);
}
cur++;
}
int x=getbound(v2[j].s.f,v2[j].f);
if(x!=-1){
t.updateadd(0,n,0,x,v2[j].s.s,1);
bruh=t.qry(0,n,x,1);
where=t.search(0,n,x+1,n,bruh,1);
if(where!=-1)t.updateset(0,n,x+1,where,bruh,1);
}
}
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:49:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
49 | void init(){for(int i=0;i<=4*(n+1);i++)lazy2[i]=inf,v[i]=minf;}
| ^
dishes.cpp:50:35: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
50 | void build(int l,int r,int pos){
| ^
dishes.cpp:57:34: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
57 | void push(int l,int r,int pos){
| ^
dishes.cpp:72:61: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
72 | void updateadd(int l,int r,int ql,int qr,int val,int pos){
| ^
dishes.cpp:85:61: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
85 | void updateset(int l,int r,int ql,int qr,int val,int pos){
| ^
dishes.cpp:98:41: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
98 | int qry(int l,int r,int qpos,int pos){
| ^
dishes.cpp:105:57: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
105 | int search(int l,int r,int ql,int qr,int val,int pos){
| ^
dishes.cpp:126:27: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
126 | int getbound(int x,int add){
| ^
dishes.cpp:135:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
135 | int32_t main(){
| ^
dishes.cpp: In function 'int32_t main()':
dishes.cpp:161: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]
161 | while(cur<gap.size()&&gap[cur].f<v2[j].f){
| ~~~^~~~~~~~~~~
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 |
247 ms |
41152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
41152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
41152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
