Submission #856068

#TimeUsernameProblemLanguageResultExecution timeMemory
856068sofijavelkovskaFancy Fence (CEOI20_fancyfence)C++14
12 / 100
1 ms604 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN=1e5, MOD=1e9+7; long long h[MAXN], w[MAXN]; bool compare(int x, int y) { //if (h[x]==h[y]) // return x<y; return h[x]<=h[y]; } long long outer(int i, long long leftsum, long long rightsum) { long long rectangles=0; rectangles=(rectangles+h[i]*w[i]%MOD*leftsum%MOD)%MOD; rectangles=(rectangles+h[i]*(h[i]-1)/2%MOD*w[i]%MOD*leftsum%MOD)%MOD; rectangles=(rectangles+h[i]*w[i]%MOD*rightsum%MOD)%MOD; rectangles=(rectangles+h[i]*(h[i]-1)/2%MOD*w[i]%MOD*rightsum%MOD)%MOD; rectangles=(rectangles+h[i]*leftsum%MOD*rightsum%MOD)%MOD; rectangles=(rectangles+h[i]*(h[i]-1)/2%MOD*leftsum%MOD*rightsum%MOD)%MOD; return rectangles; } long long inner(int i) { long long rectangles=0; rectangles=(rectangles+h[i]*w[i]%MOD)%MOD; rectangles=(rectangles+w[i]*(w[i]-1)/2%MOD*h[i]%MOD)%MOD; rectangles=(rectangles+h[i]*(h[i]-1)/2%MOD*w[i]%MOD)%MOD; rectangles=(rectangles+h[i]*(h[i]-1)/2%MOD*(w[i]*(w[i]-1)/2%MOD)%MOD)%MOD; return rectangles; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, x, left, right, i; long long leftsum, rightsum, total=0; set<int> processed; cin >> n; int index[n]; long long prefixsum[n]; for (i=0; i<n; i++) cin >> h[i]; for (i=0; i<n; i++) cin >> w[i]; for (i=0; i<n; i++) index[i]=i; sort(index, index+n, compare); prefixsum[0]=w[0]; for (i=1; i<n; i++) prefixsum[i]=prefixsum[i-1]+w[i]; processed.insert(-1); processed.insert(n); for (i=0; i<n; i++) { x=index[i]; auto it=processed.lower_bound(x); right=*it; it--; left=*it; rightsum=(prefixsum[right-1]-prefixsum[x])%MOD; leftsum=(prefixsum[x]-w[x]-(prefixsum[left+1]-w[left+1]))%MOD; total=(total+outer(x, leftsum, rightsum)+inner(x))%MOD; processed.insert(x); } cout << total; return 0; }
#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...