Submission #1012423

#TimeUsernameProblemLanguageResultExecution timeMemory
1012423modwweTwo Dishes (JOI19_dishes)C++17
100 / 100
2388 ms158544 KiB
//https://www.instagram.com/_modwwe/ #pragma GCC optimize("Ofast") //#pragma GCC target("avx2,bmi,bmi2") #include<bits/stdc++.h> #define int long long //#define ll long long #define down cout<<'\n'; #define debug cout<<" cucuucucuuu",down #define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); #define modwwe int t;cin>>t; while(t--) #define bit(i,j) (i>>j&1) #define sobit(a) __builtin_popcountll(a) #define task "test" #define fin(x) freopen(x".inp","r",stdin) #define fou(x) freopen(x".ans ","w",stdout) #define pb push_back #define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms"; using namespace std; void phongbeo(); const int inf=1e18; const int mod2=1e9+7; const int mod1=998244353; struct icd { int a,b; }; struct ib { int a; int b; }; struct ic { int a,b,c; }; struct id { int a,b,c,d; }; struct ie { int a,b,c, d,e,f; }; int n,m,s0,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l,l2,r2,l3,l4; int i,s10,s12; int el=29; main() { #ifndef ONLINE_JUDGE // fin(task),fou(task); #endif NHP /// cin>>s1; // modwwe phongbeo(),down } struct IT { ib t[4000011]; void ff(int x) { for(int i=x*2; i<=x*2+1; i++) t[i].a+=t[x].b, t[i].b+=t[x].b; t[x].b=0; } void build(int node,int l,int r) { t[node].a=-inf; if(l==0&&r==0) t[node].a=0; if(l==r) return; int mid=l+r>>1; build(node<<1,l,mid); build(node<<1|1,mid+1,r); t[node].a=max(t[node<<1].a,t[node<<1|1].a); } void upd2(int node,int l,int r,int l1,int c) { if(l==r) { t[node].a=max(t[node].a,c) ; return; } int mid=l+r>>1; ff(node); if(l1<=mid) upd2(node<<1,l,mid,l1,c); else upd2(node<<1|1,mid+1,r,l1,c); t[node].a=max(t[node<<1].a,t[node<<1|1].a); } void upd(int node,int l,int r,int l1,int r1,int c) { if(l>r1||r<l1) return; if(l>=l1&&r<=r1) { t[node].a+=c; t[node].b+=c; return; } int mid=l+r>>1; ff(node); upd(node<<1,l,mid,l1,r1,c); upd(node<<1|1,mid+1,r,l1,r1,c); t[node].a=max(t[node<<1].a,t[node<<1|1].a); } int get(int node,int l,int r,int l1,int r1) { if(l>r1||r1<l1) return -inf; if(l>=l1&&r<=r1) return t[node].a; int mid=l+r>>1; ff(node); return max(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1)); } } st; struct FEN { int bit[1000007]; void upd(int x,int y) { for(x; x<=m; x+=x&-x)bit[x]+=y; } int get(int x) { int s=0; for(x; x; x-=x&-x) s+=bit[x]; return s; } } fe; ic a[1000007]; ic b[1000007]; vector<int> v[1000007]; vector<int> v3; vector<int> v4; void phongbeo() { cin>>n>>m; for(int i=1; i<=n; i++) cin>>a[i].a>>a[i].b>>a[i].c, a[i].a+=a[i-1].a, v3.pb(a[i].a); for(int i=1; i<=m; i++) cin>>b[i].a>>b[i].b>>b[i].c, b[i].a+=b[i-1].a, v4.pb(b[i].a); st.build(1,0,m); for(int i=1; i<=m; i++) { s2=b[i].b-b[i].a; if(s2>=0) { fe.upd(i,b[i].c); s2=upper_bound(v3.begin(),v3.end(),s2)-v3.begin()+1; v[s2].pb(i); } } for(int i=1; i<=n; i++) { for(auto x:v[i]) { s2=st.get(1,0,m,0,x); st.upd2(1,0,m,x,s2); } if(a[i].b-a[i].a>=0) { s3=upper_bound(v4.begin(),v4.end(),a[i].b-a[i].a)-v4.begin(); if(s3!=m&&a[i].c<0) { s5=s3+1; s2=st.get(1,0,m,0,s5); st.upd2(1,0,m,s5,s2); } st.upd(1,0,m,0,s3,a[i].c); } for(auto x:v[i]) { fe.upd(x,-b[x].c); st.upd(1,0,m,x,m,b[x].c); } } cout<<st.t[1].a+fe.get(m); }

Compilation message (stderr)

dishes.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main()
      | ^~~~
dishes.cpp: In member function 'void IT::build(long long int, long long int, long long int)':
dishes.cpp:73:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mid=l+r>>1;
      |                 ~^~
dishes.cpp: In member function 'void IT::upd2(long long int, long long int, long long int, long long int, long long int)':
dishes.cpp:85:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         int mid=l+r>>1;
      |                 ~^~
dishes.cpp: In member function 'void IT::upd(long long int, long long int, long long int, long long int, long long int, long long int)':
dishes.cpp:100:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |         int mid=l+r>>1;
      |                 ~^~
dishes.cpp: In member function 'long long int IT::get(long long int, long long int, long long int, long long int, long long int)':
dishes.cpp:110:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid=l+r>>1;
      |                 ~^~
dishes.cpp: In member function 'void FEN::upd(long long int, long long int)':
dishes.cpp:120:13: warning: statement has no effect [-Wunused-value]
  120 |         for(x; x<=m; x+=x&-x)bit[x]+=y;
      |             ^
dishes.cpp: In member function 'long long int FEN::get(long long int)':
dishes.cpp:125:13: warning: statement has no effect [-Wunused-value]
  125 |         for(x; x; x-=x&-x) s+=bit[x];
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...