oj.uz

Submission #1008282

# Submission time Handle Problem Language Result Execution time Memory
1008282 2024-06-26T08:52:10 Z andecaandeci Fancy Fence (CEOI20_fancyfence) C++17
100 / 100
 66 ms 10668 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<ll,ll>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define freeopen freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define pb push_back
#define mk make_pair
#define ll long long
#define foor(x,vec) for(auto x:vec ){cout<<x<<" ";}
#define fi first
#define se second
#define MAXN 700069
#define lld long double
#define cha ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ffl fflush(stdout)
#define sst string
#define pii pair<ll,ll>
ll mvx[]={0,0,-1,1};
ll mvy[]={1,-1,0,0};
ll n,q;
ll a,b;
ll h[MAXN],w[MAXN];
ll ps[MAXN];
ll dp[MAXN];
ll idx[MAXN];
const ll mod =1e9+7;
ll add(ll x, ll y) {
    ll res=(x+y+mod)%mod;
    return res;
}


ll cal(ll x) {
    return (ll)((1ll * x * (x + 1) / 2) % mod);
}
ll mult(ll x, ll y) {
    return (ll)((1ll * x * y) % mod);
}


int main(){
    cin>>n;
    REP(i,1,n)cin>>h[i];
    REP(i,1,n)cin>>w[i];
    REP(i,1,n){
        ps[i]=ps[i-1]+w[i];
        ps[i]%=mod;
    }
    vector<ll> stck;
    ll ans=0;
    stck.pb(0);
    for(int i = 1; i <= n; i++) {
        while(stck.size() && h[i] < h[stck.back()]) {
            stck.pop_back();
        }
        if(stck.size())
        idx[i] = stck.back();
        stck.pb(i);
    }
    
    REP(i,1,n) {
        dp[i] = add(dp[idx[i]], mult((ps[i] - ps[idx[i]]), cal(h[i] ) ));
        ll val = mult(dp[idx[i]], w[i]);
        val = add(val, mult( (ps[i - 1]- ps[idx[i]]), mult(w[i], cal(h[i] ) ) ) );
        val = add(val, mult(cal(w[i] ), cal(h[i])));
        ans = add(ans, val);
    }
    ans=(ans+mod)%mod;
    cout<<ans<<endl;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 2492 KB Output is correct
3 Correct 20 ms 4376 KB Output is correct
4 Correct 37 ms 8076 KB Output is correct
5 Correct 46 ms 7880 KB Output is correct
6 Correct 34 ms 7660 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 5 ms 4956 KB Output is correct
3 Correct 27 ms 6292 KB Output is correct
4 Correct 64 ms 6544 KB Output is correct
5 Correct 50 ms 8228 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct

Subtask #5
15.0 / 15.0

# 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 5 ms 3036 KB Output is correct
4 Correct 24 ms 4556 KB Output is correct
5 Correct 48 ms 8236 KB Output is correct
6 Correct 55 ms 8392 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 5 ms 5212 KB Output is correct
9 Correct 25 ms 7380 KB Output is correct
10 Correct 47 ms 10168 KB Output is correct
11 Correct 51 ms 8392 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 4564 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2672 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4540 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 17 ms 4768 KB Output is correct
12 Correct 34 ms 9440 KB Output is correct
13 Correct 35 ms 8908 KB Output is correct
14 Correct 45 ms 6992 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 6 ms 3164 KB Output is correct
17 Correct 26 ms 5476 KB Output is correct
18 Correct 56 ms 8392 KB Output is correct
19 Correct 50 ms 10436 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 5 ms 4956 KB Output is correct
22 Correct 25 ms 5432 KB Output is correct
23 Correct 63 ms 8136 KB Output is correct
24 Correct 66 ms 8344 KB Output is correct
25 Correct 0 ms 2396 KB Output is correct
26 Correct 1 ms 4444 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 1 ms 4444 KB Output is correct
30 Correct 5 ms 2860 KB Output is correct
31 Correct 6 ms 4956 KB Output is correct
32 Correct 23 ms 6592 KB Output is correct
33 Correct 27 ms 4956 KB Output is correct
34 Correct 46 ms 7368 KB Output is correct
35 Correct 39 ms 9296 KB Output is correct
36 Correct 50 ms 9296 KB Output is correct
37 Correct 42 ms 9296 KB Output is correct
38 Correct 1 ms 4440 KB Output is correct
39 Correct 42 ms 7516 KB Output is correct
40 Correct 41 ms 10668 KB Output is correct
41 Correct 43 ms 9528 KB Output is correct
42 Correct 41 ms 9756 KB Output is correct