#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];
mint sum = 0;
stack<pll> stk; //h, w
mint calc(mint H, mint W) {
return (H*(H+1)/2)*(W*(W+1)/2);
}
mint calc2(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];
stk.push({h[1], w[1]});
for (int i = 2; i <= n; ++i) {
ll curw = w[i];
while(!stk.empty() && stk.top().st >= h[i]) {
auto [H, W] = stk.top(); stk.pop();
ll next_h = (stk.empty() ? 0 : stk.top().st);
curw += W;
sum += calc(H-next_h, curw);
sum += calc2(H-next_h, next_h, curw);
}
stk.push({h[i], curw});
}
ll curw = 0;
while(!stk.empty()) {
auto [H, W] = stk.top(); stk.pop();
curw += W;
sum += calc(H-(stk.empty()?0:stk.top().st), curw);
if (!stk.empty()) sum += calc2(H-stk.top().st, stk.top().st, curw);
}
cout << sum << 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:118:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
118 | auto [H, W] = stk.top(); stk.pop();
| ^
fancyfence.cpp:128:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
128 | auto [H, W] = stk.top(); stk.pop();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
380 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
