Submission #702657

#TimeUsernameProblemLanguageResultExecution timeMemory
702657a_aguiloFancy Fence (CEOI20_fancyfence)C++14
100 / 100
99 ms5448 KiB
#include<bits/stdc++.h> using namespace std; int n; int MOD = 1e9 + 7; long long calcOwnRectangles(long long int h, long long int w, long long int addition){ long long chooseH = (h*(h+1)/2)%MOD; long long chooseW = ((w*(w+1)/2)%MOD + (addition*w)%MOD )%MOD; long long ans = (chooseH*chooseW)%MOD; return ans; } long long getEndings(long long h, long long w){ long long WOptions = w; long long HOptions = (h*(h+1)/2)%MOD; long long ans = (WOptions*HOptions)%MOD; return ans; } int main(){ cin >> n; int heights[n]; int widths[n]; long long dp[n]; long long int ans = 0; for(int i = 0; i < n; ++i) cin >> heights[i]; for(int i = 0; i < n; ++i) cin >> widths[i]; vector<pair<long long int, long long int>> MyStack; MyStack.reserve(n); for(int i = 0; i < n; ++i){ long long int myH = heights[i]; long long int myW = widths[i]; long long addW = 0; int lPos = MyStack.size()-1; while(lPos >= 0 and MyStack[lPos].first > myH){ addW += MyStack[lPos].second; addW %= MOD; MyStack.pop_back(); lPos = MyStack.size()-1; } MyStack.push_back({myH, myW+addW}); long long indepRectangles = calcOwnRectangles(myH, myW, addW); ans += indepRectangles; ans %= MOD; //cout << myH << " " << myW << " "<< ans << endl; dp[MyStack.size()-1] = getEndings(myH, (myW+addW)%MOD); if(MyStack.size() == 1){ //Este es el primero continue; }else{ //Este NO es el primero --> para los rectángulos se pueden continuar los que acaban en el anterior ans += (dp[MyStack.size()-2]*myW)%MOD; ans %= MOD; //Tambien se puede hacer que el numero de los que acaban en esta posicion incorpore los que acaban en la anterior dp[MyStack.size()-1] += dp[MyStack.size()-2]; dp[MyStack.size()-1] %= MOD; } //cout << myH << " " << ans << endl; } cout << ans << endl; 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...