제출 #1020270

#제출 시각아이디문제언어결과실행 시간메모리
1020270modwweBitaro, who Leaps through Time (JOI19_timeleap)C++17
100 / 100
442 ms95756 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".out","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,s1,s2,s4,s3,sf,k,r,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,l,l2,r2; int i,s10,s12; int el=29; main() { #ifndef ONLINE_JUDGE // fin(task),fou(task); #endif NHP /// cin>>s1; // modwwe phongbeo(); } id ss,ss2; ib a[300001]; ib b[300001]; id mer(id x,id y,int c) { id s; /// a.d= if(l+a.d) b=b -> l+a.d+x ->b=b+x ///a.a= if(l+a.a) c=c -> l+a.a+x ->c=c+x /// a.a=min(x.a,y.a+x.d) /// a.d=x.d+y.d if(x.b>=c) { s2=x.b-c; s.c=x.c+y.c; ///cout<<y.d<<" "<<y.a,down if(s2>y.a) { s.c+=s2-y.a; y.b-=s2-y.a; y.a=0; } else y.a-=s2; s.b=y.b; if(s2>y.d) { s.b+=s2-y.d; y.d=0; } else y.d-=s2; } else { s.b=y.b; x.d+=c-x.b; s.c=x.c+y.c; } s.a=min(x.a,y.a+x.d); s.d=x.d+y.d; s.d=min(s.d,s.a); return s; } struct IT { id t[1200001]; void build(int node,int l,int r) { if(l==r) { t[node].a=a[l].b-a[l].a; t[node].b=a[l].a+1; t[node].c=0; t[node].d=0; return; } int mid=l+r>>1; build(node<<1,l,mid); build(node<<1|1,mid+1,r); t[node]=mer(t[node<<1],t[node<<1|1],a[mid+1].a); } void upd(int node,int l,int r,int l1) { if(l==r) { t[node].a=a[l].b-a[l].a; t[node].b=a[l].a+1; t[node].c=0; t[node].d=0; return; } int mid=l+r>>1; if(l1<=mid)upd(node<<1,l,mid,l1); else upd(node<<1|1,mid+1,r,l1); t[node]=mer(t[node<<1],t[node<<1|1],a[mid+1].a); } void get(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return; if(l>=l1&&r<=r1) { ss=mer(ss,t[node],a[l].a);return;} int mid=l+r>>1; get(node<<1,l,mid,l1,r1); get(node<<1|1,mid+1,r,l1,r1); } }st; struct IT2 { id t[1200001]; void build(int node,int l,int r) { if(l==r) { t[node].a=b[l].b-b[l].a; t[node].b=b[l].a+1; t[node].c=0; t[node].d=0; return; } int mid=l+r>>1; build(node<<1,l,mid); build(node<<1|1,mid+1,r); t[node]=mer(t[node<<1],t[node<<1|1],b[mid+1].a); } void upd(int node,int l,int r,int l1) { if(l==r) { t[node].a=b[l].b-b[l].a; t[node].b=b[l].a+1; t[node].c=0; t[node].d=0; return; } int mid=l+r>>1; if(l1<=mid)upd(node<<1,l,mid,l1); else upd(node<<1|1,mid+1,r,l1); t[node]=mer(t[node<<1],t[node<<1|1],b[mid+1].a); } void get(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1) return; if(l>=l1&&r<=r1) { ss=mer(ss,t[node],b[l].a);return;} int mid=l+r>>1; get(node<<1,l,mid,l1,r1); get(node<<1|1,mid+1,r,l1,r1); } }st2; void phongbeo() { cin>>n>>m; for(int i=1; i<n; i++) cin>>a[i].a>>a[i].b,a[i].b--,b[n-i]=a[i]; if(n!=1) st.build(1,1,n-1); if(n!=1)st2.build(1,1,n-1); while(m--) { cin>>l; if(l==1) { cin>>l>>s2>>s3; a[l]={s2,s3-1}; b[n-l]=a[l]; if(n!=1) st.upd(1,1,n-1,l); if(n!=1)st2.upd(1,1,n-1,n-l); } else { cin>>l>>r>>l2>>r2; if(l==l2) cout<<max(0ll,r-r2); else{ ss2={r2,1,0,0}; ss={0,r,0,0}; if(l<=l2) st.get(1,1,n-1,l,l2-1); else {l=n-l+1;l2=n-l2+1; st2.get(1,1,n-1,l,l2-1); } cout<<mer(ss,ss2,0).c;} down } } }

컴파일 시 표준 에러 (stderr) 메시지

timeleap.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main()
      | ^~~~
timeleap.cpp: In member function 'void IT::build(long long int, long long int, long long int)':
timeleap.cpp:112:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |         int mid=l+r>>1;
      |                 ~^~
timeleap.cpp: In member function 'void IT::upd(long long int, long long int, long long int, long long int)':
timeleap.cpp:127:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |  int mid=l+r>>1;
      |          ~^~
timeleap.cpp: In member function 'void IT::get(long long int, long long int, long long int, long long int, long long int)':
timeleap.cpp:137:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |            int mid=l+r>>1;
      |                    ~^~
timeleap.cpp: In member function 'void IT2::build(long long int, long long int, long long int)':
timeleap.cpp:156:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  156 |         int mid=l+r>>1;
      |                 ~^~
timeleap.cpp: In member function 'void IT2::upd(long long int, long long int, long long int, long long int)':
timeleap.cpp:171:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  171 |  int mid=l+r>>1;
      |          ~^~
timeleap.cpp: In member function 'void IT2::get(long long int, long long int, long long int, long long int, long long int)':
timeleap.cpp:181:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  181 |            int mid=l+r>>1;
      |                    ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...