Submission #855562

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