제출 #1012409

#제출 시각아이디문제언어결과실행 시간메모리
1012409modwweTwo Dishes (JOI19_dishes)C++17
100 / 100
3212 ms262976 KiB
//https://www.instagram.com/_modwwe/ #pragma GCC optimize("Ofast,unroll-loops") //#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 { id 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[i].c+=t[x].d, t[i].d+=t[x].d; t[x].d=0; t[x].b=0; } void build(int node,int l,int r) { t[node].a=-inf; t[node].c=-inf; if(l==0&&r==0) t[node].a=0,t[node].c=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); t[node].c=max(t[node<<1].c,t[node<<1|1].c); } void upd2(int node,int l,int r,int l1,int c,int y) { if(l==r) { t[node].a=max(t[node].a,c) ; t[node].c=max(t[node].c,y); return; } int mid=l+r>>1; ff(node); if(l1<=mid) upd2(node<<1,l,mid,l1,c,y); else upd2(node<<1|1,mid+1,r,l1,c,y); t[node].a=max(t[node<<1].a,t[node<<1|1].a); t[node].c=max(t[node<<1].c,t[node<<1|1].c); } 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; /// t[node].c+=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); t[node].c=max(t[node<<1].c,t[node<<1|1].c); } void upd3(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; t[node].d+=c; t[node].c+=c; return; } int mid=l+r>>1; ff(node); upd3(node<<1,l,mid,l1,r1,c); upd3(node<<1|1,mid+1,r,l1,r1,c); t[node].a=max(t[node<<1].a,t[node<<1|1].a); t[node].c=max(t[node<<1].c,t[node<<1|1].c); } 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+1; i++) { for(auto x:v[i]) { s2=st.get(1,0,m,0,x); s3=fe.get(x); st.upd2(1,0,m,x,s2,s2+s3); } if(i==n+1) break; 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) { s5=s3+1; s2=st.get(1,0,m,0,s5); s4=fe.get(s5); st.upd2(1,0,m,s5,s2,s2+s4); } st.upd3(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.get(1,0,m,0,m)+fe.get(m); }

컴파일 시 표준 에러 (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:77:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         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, long long int)':
dishes.cpp:91:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         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:108:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |         int mid=l+r>>1;
      |                 ~^~
dishes.cpp: In member function 'void IT::upd3(long long int, long long int, long long int, long long int, long long int, long long int)':
dishes.cpp:127:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |         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:139:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |         int mid=l+r>>1;
      |                 ~^~
dishes.cpp: In member function 'void FEN::upd(long long int, long long int)':
dishes.cpp:149:13: warning: statement has no effect [-Wunused-value]
  149 |         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:154:13: warning: statement has no effect [-Wunused-value]
  154 |         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...