Submission #1005064

#TimeUsernameProblemLanguageResultExecution timeMemory
1005064emptypringlescanFlooding Wall (BOI24_wall)C++17
58 / 100
5048 ms29864 KiB
#include <bits/stdc++.h> using namespace std; const long long mod=1000000007; long long twok[500005]; int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; pair<long long,long long> arr[n]; for(int i=0; i<n; i++) cin >> arr[i].first; for(int i=0; i<n; i++) cin >> arr[i].second; vector<pair<long long,int> > hei; for(int i=0; i<n; i++){ if(arr[i].first>arr[i].second)swap(arr[i].first,arr[i].second); hei.push_back({arr[i].first,i}); hei.push_back({arr[i].second,i}); } sort(hei.begin(),hei.end(),greater<pair<long long,int> >()); long long ans=0; int st[n],add1[n],add2[n]; memset(add1,0,sizeof(add1)); memset(add2,0,sizeof(add2)); for(int i=0; i<n; i++) st[i]=2; for(auto [h,i]:hei){ long long mult=1; for(int j=0; j<i; j++) mult=mult*st[j]%mod; for(int j=i+1; j<n; j++){ if(h>arr[j].first){ ans+=mult*add1[j]%mod*(h-arr[j].first)%mod; } if(h>arr[j].second){ ans+=mult*add1[j]%mod*(h-arr[j].second)%mod; } add2[j]+=mult; if(add2[j]>=mod) add2[j]-=mod; mult=mult*st[j]%mod; } mult=1; for(int j=i+1; j<n; j++) mult=mult*st[j]%mod; for(int j=i-1; j>=0; j--){ if(h>arr[j].first){ ans+=mult*add2[j]%mod*(h-arr[j].first)%mod; } if(h>arr[j].second){ ans+=mult*add2[j]%mod*(h-arr[j].second)%mod; } add1[j]+=mult; if(add1[j]>=mod) add1[j]-=mod; mult=mult*st[j]%mod; } st[i]--; } ans%=mod; cout << ans; }
#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...