제출 #1065405

#제출 시각아이디문제언어결과실행 시간메모리
1065405modwweFlooding Wall (BOI24_wall)C++17
100 / 100
2534 ms219640 KiB
//https://www.instagram.com/_modwwe/ #pragma GCC optimize("Ofast,unroll-loops") #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=1e9; const int mod2=1e9+7; const int mod1=998244353; struct icd { long double a; int 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; }; int n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid; int i,s10,s12; int kk; int el=29; main() { #ifndef ONLINE_JUDGE //fin(task),fou(task); #endif NHP /// cin>>s1; // modwwe phongbeo(); } vector<int> v; int add(int x,int y) { if(x+y>=mod2) x-=mod2; if(x+y<0) x+=mod2; return x+y; } id mer(id a,id b) { return {add(a.a,b.a),add(a.b,b.b),add(a.c,b.c),add(a.d,b.d)}; } struct IT { id t[4000001]; int t2[4000001]; int t3[4000001]; void build() { for(int node=1;node<=4*m;node++) {t2[node]=1; t[node]= {0,0,0,0}; t3[node]=0; } } void ff(int x) { for(int i=x*2; i<=x*2+1; i++) { if(t2[i]==0) continue; t[i].a=t[i].a*t2[x]%mod2; t[i].b=t[i].b*t2[x]%mod2; t2[i]=t2[i]*t2[x]%mod2; t3[i]=(t3[i]+t3[x])%mod2; t[i].c=(t[i].c*t2[x])%mod2; t[i].d=(t[i].d*t2[x])%mod2; t[i].c=(t[i].c-(t3[x]*t[i].d)%mod2)%mod2; } t2[x]=1; t3[x]=0; } void upd(int node,int l,int r,int l1,int r1,int x) { if(l>r1||r<l1||!t2[node]) return; if(l>=l1&&r<=r1) { t[node].b=t[node].b*2%mod2; t[node].a=t[node].a*2%mod2; t2[node]=t2[node]*2%mod2; t[node].c=t[node].c*2%mod2; t[node].d=t[node].d*2%mod2; t3[node]+=x; t[node].c-=(x*t[node].d)%mod2; t3[node]%=mod2; t[node].c%=mod2; return; } if(t2[node]!=1||t3[node]!=0) ff(node); int mid=l+r>>1; upd(node<<1,l,mid,l1,r1,x); upd(node<<1|1,mid+1,r,l1,r1,x); t[node]=mer(t[node<<1],t[node<<1|1]); } void upd2(int node,int l,int r,int l1,ib x,int g) {if(!t2[node]) return; if(l==r) { t[node].c+=x.a; t[node].b+=(((g*v[l-1])%mod2)*x.b)%mod2; t[node].a+=(x.b*v[l-1])%mod2; t[node].d+=x.b; t[node].a%=mod2; t[node].b%=mod2; t[node].d%=mod2; t[node].c%=mod2; return; } int mid=l+r>>1; if(t2[node]!=1||t3[node]!=0) ff(node); if(l1<=mid) upd2(node<<1,l,mid,l1,x,g); else upd2(node<<1|1,mid+1,r,l1,x,g); t[node]=mer(t[node<<1],t[node<<1|1]); } void upd3(int node,int l,int r,int l1,int r1,int x) { if(l>r1||r<l1||!t2[node]) return; if(l>=l1&&r<=r1) { t[node].c-=(x*t[node].d)%mod2; t[node].c%=mod2; t3[node]+=x; t3[node]%=mod2; return; } int mid=l+r>>1; if(t2[node]!=1||t3[node]!=0) ff(node); upd3(node<<1,l,mid,l1,r1,x); upd3(node<<1|1,mid+1,r,l1,r1,x); t[node]=mer(t[node<<1],t[node<<1|1]); } void del(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1||!t2[node]) return; if(l>=l1&&r<=r1) { t2[node]=0; t[node]= {0,0,0,0}; return; } int mid=l+r>>1; if(t2[node]!=1||t3[node]!=0) ff(node); del(node<<1,l,mid,l1,r1); del(node<<1|1,mid+1,r,l1,r1); t[node]=mer(t[node<<1],t[node<<1|1]); } id get(int node,int l,int r,int l1,int r1) { if(l>r1||r<l1||!t2[node]) return {0,0,0,0}; if(l>=l1&&r<=r1) return t[node]; int mid=l+r>>1; if(t2[node]!=1||t3[node]!=0) ff(node); return mer(get(node<<1,l,mid,l1,r1),get(node<<1|1,mid+1,r,l1,r1)); } } st; ib a[500001]; struct ibb{ ib a,b; }c[500001]; int invf2; int ipow(int x, int p){ int ret = 1, piv = x; while(p){ if(p&1) ret *= piv; piv *= piv; ret %= mod2; piv %= mod2; p >>= 1; } return ret; } void phongbeo() { cin>>n; for(int i=1; i<=n; i++) cin>>a[i].a,v.pb(a[i].a); for(int i=1; i<=n; i++) cin>>a[i].b,v.pb(a[i].b); sort(v.begin(),v.end()); v.erase(unique(v.begin(), v.end()), v.end()); m=v.size(); for(int i=1; i<=n; i++) { if(a[i].a>a[i].b) swap(a[i].a,a[i].b); a[i].a=lower_bound(v.begin(),v.end(),a[i].a)-v.begin()+1; a[i].b=lower_bound(v.begin(),v.end(),a[i].b)-v.begin()+1; } st.build(); st.upd2(1,1,m,a[n].b,{-v[a[n].b-1],1},n); st.upd2(1,1,m,a[n].a,{-v[a[n].a-1],1},n); st.del(1,1,m,1,a[n].a-1); c[n].a={0,1}; c[n].b={0,1}; invf2=ipow(2,mod2-2); for(int i=n-1; i>=1; --i) { id x=st.get(1,1,m,1,a[i].a-1); id x2=st.get(1,1,m,1,a[i].b-1); st.upd(1,1,m,a[i].b,m,((v[a[i].a-1]+v[a[i].b-1])%mod2*invf2)%mod2); st.upd3(1,1,m,a[i].a,a[i].b-1,v[a[i].a-1]); st.del(1,1,m,1,a[i].a-1); s2=(x.c+x.b-x.a*i)%mod2; s3=(x2.c+x2.b-x2.a*i)%mod2; c[i].a={s2,x.d}; c[i].b={s3,x2.d}; if(x.d!=0) st.upd2(1,1,m,a[i].a,{(s2-(v[a[i].a-1]*x.d)%mod2)%mod2,x.d},i); if(x2.d!=0) st.upd2(1,1,m,a[i].b,{(s3-(v[a[i].b-1]*x2.d)%mod2)%mod2,x2.d},i); } s4=0; for(int i=0;i<=n-1;i++) { if(i==0) { s4=(s4+c[1].a.a+c[1].b.a)%mod2; } else { if(i==1) { st.build(); st.upd2(1,1,m,a[1].b,{-v[a[1].b-1],1},1); st.upd2(1,1,m,a[1].a,{-v[a[1].a-1],1},1); st.del(1,1,m,1,a[1].a-1); } else { id x=st.get(1,1,m,1,a[i].a-1); id x2=st.get(1,1,m,1,a[i].b-1); st.upd(1,1,m,a[i].b,m,((v[a[i].a-1]+v[a[i].b-1])%mod2*invf2)%mod2); st.upd3(1,1,m,a[i].a,a[i].b-1,v[a[i].a-1]); st.del(1,1,m,1,a[i].a-1); s2=(x.c+(x.a*i)%mod2-x.b)%mod2; s3=(x2.c+(x2.a*i)%mod2-x2.b)%mod2; if(x.d!=0) st.upd2(1,1,m,a[i].a,{(s2-(v[a[i].a-1]*x.d)%mod2)%mod2,x.d},i); if(x2.d!=0) st.upd2(1,1,m,a[i].b,{(s3-(v[a[i].b-1]*x2.d)%mod2)%mod2,x2.d},i); } id x=st.get(1,1,m,1,a[i+1].a); s2=(x.c+(x.a*i+x.a)%mod2-x.b)%mod2; s4=(s4+(x.d*c[i+1].a.a%mod2+s2*c[i+1].a.b%mod2))%mod2; x=st.get(1,1,m,1,a[i+1].b); s2=(x.c+(x.a*i+x.a)%mod2-x.b)%mod2; s4=(s4+x.d*c[i+1].b.a%mod2+s2*c[i+1].b.b%mod2)%mod2; } } cout<<(s4%mod2+mod2)%mod2; }

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

Main.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main()
      | ^~~~
Main.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)':
Main.cpp:118:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |         int mid=l+r>>1;
      |                 ~^~
Main.cpp: In member function 'void IT::upd2(long long int, long long int, long long int, long long int, ib, long long int)':
Main.cpp:137:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |         int mid=l+r>>1;
      |                 ~^~
Main.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)':
Main.cpp:154:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  154 |         int mid=l+r>>1;
      |                 ~^~
Main.cpp: In member function 'void IT::del(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:169:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  169 |         int mid=l+r>>1;
      |                 ~^~
Main.cpp: In member function 'id IT::get(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:180:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  180 |         int mid=l+r>>1;
      |                 ~^~
#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...