#pragma once
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef vector<vi> vvi;
template<typename T> using pq = priority_queue<T>;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
#define ins insert
template<typename T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7;
const int INF = 0x3fffffff;
const ll LINF = 0x1fffffffffffffff;
const char nl = '\n';
const int MX = 1e5 + 3;
ll modmul(ll a,ll b,ll mod){
ll res=(a*b-ll(1.l*a*b/mod)*mod)%mod;
if(res<0)res+=mod;
return res;
}
ll modinv(ll a, ll b) {
ll x=0,x1=1;
while(a!=0){
ll q=b/a;
b-=q*a; x-=q*x1;
swap(a,b); swap(x,x1);
}
return x;
}
template<ll M>
struct Mint{
ll x;
constexpr Mint():x(0){}
constexpr Mint(ll x):x(norm(x%getMod())){}
static ll Mod;
constexpr static ll getMod(){return M>0?M:Mod;}
constexpr static void setMod(ll Mod_){Mod=Mod_;}
constexpr ll norm(ll x)const{if(x<0)x+=getMod();if(x>=getMod())x-=getMod();return x;}
explicit constexpr operator ll()const{return x;}
constexpr Mint operator-()const{Mint res;res.x=norm(-x);return res;}
constexpr Mint inv()const{return modinv(x,getMod());}
constexpr Mint &operator+=(const Mint &rhs){x=norm(x+rhs.x);return *this;}
constexpr Mint &operator-=(const Mint &rhs){x=norm(x-rhs.x);return *this;}
constexpr Mint &operator*=(const Mint &rhs){x=modmul(x,rhs.x,getMod());return *this;}
constexpr Mint &operator/=(const Mint &rhs){x=modmul(x,rhs.inv().x,getMod());return *this;}
constexpr Mint &operator++(){return *this+=1;}
constexpr Mint &operator--(){return *this-=1;}
constexpr Mint operator++(int){Mint res=*this;*this+=1;return res;}
constexpr Mint operator--(int){Mint res=*this;*this-=1;return res;}
friend constexpr Mint operator+(Mint lhs,const Mint &rhs){return lhs+=rhs;}
friend constexpr Mint operator-(Mint lhs,const Mint &rhs){return lhs-=rhs;}
friend constexpr Mint operator*(Mint lhs,const Mint &rhs){return lhs*=rhs;}
friend constexpr Mint operator/(Mint lhs,const Mint &rhs){return lhs/=rhs;}
friend istream &operator>>(istream &is,Mint &o){ll x{};is>>x;o=Mint(x);return is;}
friend ostream &operator<<(ostream &os,const Mint &o){return os<<o.x;}
friend constexpr bool operator==(const Mint &lhs,const Mint &rhs){return lhs.x==rhs.x;}
friend constexpr bool operator!=(const Mint &lhs,const Mint &rhs){return lhs.x!=rhs.x;}
friend constexpr bool operator<(const Mint &lhs,const Mint &rhs){return lhs.x<rhs.x;} // for std::map
};
template<>
ll Mint<0ll>::Mod=ll(1e18)+9;
using mint = Mint<MOD>;
using vm = vector<mint>;
mint invmod(int x){
static vm invs{0,1};
for(int i=sz(invs);i<=x;i++)
invs.push_back(-MOD/i*invs[MOD%i]);
return invs[x];
}
ll h[MX], w[MX], sz;
pll stk[MX]; //h, w
mint calc(mint H, mint W) {
return (H*(H+1)/2)*(W*(W+1)/2);
}
mint calc(mint H, mint Hp, mint W) {
return H*Hp*(W*(W+1)/2);
}
void solve() {
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> h[i];
for (int i = 1; i <= n; ++i) cin >> w[i];
mint ans = 0;
stk[++sz] = {h[1], w[1]};
for (int i = 2; i <= n; ++i) {
ll curw = 0;
while(sz && stk[sz].st >= h[i]) {
auto [H, W] = stk[sz--];
ll dif = (H-max(h[i], stk[sz].st));
curw += W;
ans += calc(dif, curw) + calc(dif, H-dif, curw);
}
curw += w[i];
stk[++sz] = {h[i], curw};
}
ll curw = 0;
while(sz) {
auto [H, W] = stk[sz--];
ll dif = (H-stk[sz].st);
curw += W;
ans += calc(dif, curw) + calc(dif, H-dif, curw);
}
cout << ans << nl;
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0); cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--) { solve(); }
return 0;
}
Compilation message
fancyfence.cpp:1:9: warning: #pragma once in main file
1 | #pragma once
| ^~~~
fancyfence.cpp: In function 'void solve()':
fancyfence.cpp:117:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
117 | auto [H, W] = stk[sz--];
| ^
fancyfence.cpp:127:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
127 | auto [H, W] = stk[sz--];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
17 ms |
3424 KB |
Output is correct |
4 |
Correct |
34 ms |
4444 KB |
Output is correct |
5 |
Correct |
34 ms |
4440 KB |
Output is correct |
6 |
Correct |
35 ms |
4584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
4 ms |
2800 KB |
Output is correct |
3 |
Correct |
20 ms |
3668 KB |
Output is correct |
4 |
Correct |
39 ms |
4428 KB |
Output is correct |
5 |
Correct |
39 ms |
4584 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
4 ms |
2652 KB |
Output is correct |
4 |
Correct |
22 ms |
3676 KB |
Output is correct |
5 |
Correct |
38 ms |
4564 KB |
Output is correct |
6 |
Correct |
45 ms |
4676 KB |
Output is correct |
7 |
Correct |
1 ms |
2392 KB |
Output is correct |
8 |
Correct |
5 ms |
2908 KB |
Output is correct |
9 |
Correct |
20 ms |
3684 KB |
Output is correct |
10 |
Correct |
39 ms |
4408 KB |
Output is correct |
11 |
Correct |
40 ms |
4724 KB |
Output is correct |
12 |
Correct |
1 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2556 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2552 KB |
Output is correct |
11 |
Correct |
1 ms |
2396 KB |
Output is correct |
12 |
Correct |
1 ms |
2392 KB |
Output is correct |
13 |
Correct |
1 ms |
2392 KB |
Output is correct |
14 |
Correct |
1 ms |
2552 KB |
Output is correct |
15 |
Correct |
1 ms |
2648 KB |
Output is correct |
16 |
Correct |
1 ms |
2392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2520 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
2 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2524 KB |
Output is correct |
11 |
Correct |
22 ms |
3420 KB |
Output is correct |
12 |
Correct |
34 ms |
4588 KB |
Output is correct |
13 |
Correct |
34 ms |
4440 KB |
Output is correct |
14 |
Correct |
40 ms |
4448 KB |
Output is correct |
15 |
Correct |
1 ms |
2396 KB |
Output is correct |
16 |
Correct |
6 ms |
2652 KB |
Output is correct |
17 |
Correct |
19 ms |
3676 KB |
Output is correct |
18 |
Correct |
37 ms |
5212 KB |
Output is correct |
19 |
Correct |
46 ms |
5720 KB |
Output is correct |
20 |
Correct |
1 ms |
2396 KB |
Output is correct |
21 |
Correct |
5 ms |
2792 KB |
Output is correct |
22 |
Correct |
21 ms |
3928 KB |
Output is correct |
23 |
Correct |
41 ms |
5208 KB |
Output is correct |
24 |
Correct |
37 ms |
5468 KB |
Output is correct |
25 |
Correct |
1 ms |
2392 KB |
Output is correct |
26 |
Correct |
1 ms |
2592 KB |
Output is correct |
27 |
Correct |
2 ms |
2396 KB |
Output is correct |
28 |
Correct |
1 ms |
2392 KB |
Output is correct |
29 |
Correct |
1 ms |
2396 KB |
Output is correct |
30 |
Correct |
4 ms |
2652 KB |
Output is correct |
31 |
Correct |
4 ms |
2652 KB |
Output is correct |
32 |
Correct |
19 ms |
3788 KB |
Output is correct |
33 |
Correct |
19 ms |
3796 KB |
Output is correct |
34 |
Correct |
44 ms |
4952 KB |
Output is correct |
35 |
Correct |
48 ms |
4964 KB |
Output is correct |
36 |
Correct |
53 ms |
5184 KB |
Output is correct |
37 |
Correct |
37 ms |
5344 KB |
Output is correct |
38 |
Correct |
0 ms |
2396 KB |
Output is correct |
39 |
Correct |
37 ms |
5320 KB |
Output is correct |
40 |
Correct |
40 ms |
5324 KB |
Output is correct |
41 |
Correct |
37 ms |
5464 KB |
Output is correct |
42 |
Correct |
48 ms |
5692 KB |
Output is correct |