Submission #1197459

#TimeUsernameProblemLanguageResultExecution timeMemory
1197459nvc2k8Fancy Fence (CEOI20_fancyfence)C++20
100 / 100
16 ms2632 KiB
#include <bits/stdc++.h> #define TASK "kasjdkasd" #define INT_LIM (int) 2147483647 #define LL_LIM (long long) 9223372036854775807 #define ll long long #define pii pair<int,int> #define endl '\n' #define mp make_pair #define pb push_back #define fi first #define se second #define BIT(i,x) (((i)>>(x))&1) #define FOR(i,a,b) for(int i = (a); i<=(b); i++) #define FORD(i,a,b) for(int i = (a); i>=(b); i--) using namespace std; ///------------------------------------------/// const int MOD = 1e9+7; const int div2 = 500000004; int pw(int x, int p) { int ret = 1; while (p>0) { if (p&1) ret = 1LL*ret*x%MOD; x = 1LL*x*x%MOD; p>>=1; } return ret; } void add(int &x, const int &y) { x+=y; if (x>=MOD) x-=MOD; } int n; int h[100005], w[100005]; int pre[100005], nx[100005]; stack<int> st; void inp() { cin >> n; FOR(i, 1, n) { cin >> h[i]; } FOR(i, 1, n) { cin >> w[i]; } FOR(i, 1, n) { while (!st.empty() && h[st.top()]>=h[i]) st.pop(); if (st.empty()) pre[i] = 1; else pre[i] = st.top()+1; st.push(i); } while (!st.empty()) st.pop(); FORD(i, n, 1) { while (!st.empty() && h[st.top()]>h[i]) st.pop(); if (st.empty()) nx[i] = n; else nx[i] = st.top()-1; st.push(i); } } int ans = 0; int pf[100005]; int sum(int x) { return 1LL*x*(x+1)%MOD*div2%MOD; } void solve() { FOR(i, 1, n) { pf[i] = w[i]; add(pf[i], pf[i-1]); } FOR(i, 1, n) { add(ans, 1LL*sum(h[i])*sum(w[i])%MOD); int tmp = 0; int L = 0, R = 0; if (pre[i]<i) L = (pf[i-1]-pf[pre[i]-1]+MOD)%MOD; if (nx[i]>i) R = (pf[nx[i]]-pf[i]+MOD)%MOD; add(tmp, 1LL*L*R%MOD); add(tmp, 1LL*w[i]*(L+R)%MOD); add(ans, 1LL*sum(h[i])*tmp%MOD); } cout << ans; } signed main() { ///--------------------------/// ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen(TASK".INP","r")!=NULL) { freopen(TASK".INP","r",stdin); freopen(TASK".OUT","w",stdout); } ///--------------------------/// int NTEST = 1; //cin >> NTEST; while (NTEST--) { inp(); solve(); } return 0; } ///------------------------------------------///

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(TASK".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(TASK".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...