# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
881373 | 2023-12-01T07:57:08 Z | arashMLG | Fancy Fence (CEOI20_fancyfence) | C++17 | 2 ms | 8792 KB |
#include<bits/stdc++.h> #ifdef LOCAL #include "Essentials/algo/debug.h" #else #define debug(...) 69 #endif using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N = 5e5 + 23; const ll mod = 1e9 + 7; const ll inf = 1e18; #define F first #define S second #define pb push_back #define kill(x) cout<<x<<endl, exit(0); #define all(x) x.begin(),x.end() #define sz(x) (int)x.size() #define lc (v << 1) #define rc ((v<<1) |1) #define int ll void ok(int &x) { while(x <0) x += mod; x %=mod; } int n; int h[N],w[N]; int l[N],r[N]; stack<int> st; int ps[N]; int32_t main() { cin.tie(nullptr)->sync_with_stdio(false); cin>>n; for(int i = 1; i<= n ; i++) cin>>h[i]; for(int i = 1; i<= n ; i++) cin>>w[i]; for(int i = 1; i<= n ; i++) { ok(ps[i] = w[i] + ps[i-1]); } int ans=0; h[0] = -inf,h[n+1] = -inf; st.push(0); for(int i = 1; i<= n; i++) { while(h[st.top()] >= h[i]) st.pop(); l[i] = st.top(); st.push(i); } while(sz(st)) st.pop(); st.push(n+1); for(int i = n; i >= 1; i--) { while(h[st.top()] > h[i]) st.pop(); r[i] = st.top(); st.push(i); } for(int i = 1; i<= n ; i++) { int x = h[i] * (h[i]+1)/2 %mod; ok(ans += (w[i] * (w[i]+1)/2-1) %mod * x %mod); int one = (ps[i-1]- ps[l[i]] + 1 + 2 * mod) %mod; int two = (ps[r[i]-1] - ps[i] + 1 + 2 *mod) %mod; debug(one,two,x); ok(ans += one*two%mod * x %mod); } cout<<ans << '\n'; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 8540 KB | Output is correct |
2 | Incorrect | 2 ms | 8540 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 8540 KB | Output is correct |
2 | Correct | 1 ms | 8540 KB | Output is correct |
3 | Correct | 1 ms | 8536 KB | Output is correct |
4 | Correct | 1 ms | 8540 KB | Output is correct |
5 | Correct | 1 ms | 8540 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 8540 KB | Output is correct |
2 | Incorrect | 1 ms | 8540 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 8540 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 8792 KB | Output is correct |
2 | Incorrect | 1 ms | 8540 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 8792 KB | Output is correct |
2 | Incorrect | 1 ms | 8540 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 8540 KB | Output is correct |
2 | Incorrect | 2 ms | 8540 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |