oj.uz

Submission #659450

# Submission time Handle Problem Language Result Execution time Memory
659450 2022-11-17T19:35:10 Z Lobo Fancy Fence (CEOI20_fancyfence) C++17
100 / 100
 138 ms 17044 KB 
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 1e5+10;
const int mod = 1e9+7;

int n, h[maxn], w[maxn], ps[maxn];
map<int,vector<int>> ed;

int vz(int a, int b) {
    return a*b%mod;
}

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> h[i];
        ed[h[i]].pb(i);
    }
    for(int i = 1; i <= n; i++) {
        cin >> w[i];
        ps[i] = ps[i-1]+w[i]; ps[i]%= mod;
    }
    set<pair<int,int>> st;
    st.insert(mp(1,n));
    int curw = ps[n]*(ps[n]+1)/2; curw%= mod;
    int ant = 0;
    int ans = 0;
    for(auto X : ed) {
        int val = X.fr;
        // l = ant+1 r = val
        int aux = (val-ant)*(val+ant+1)/2;
        aux%= mod;
        curw%= mod;
        ans+= (curw*aux)%mod; ans%= mod;
        ant = val;
        for(auto i : X.sc) {
            auto it = st.upper_bound(mp(i,inf)); it--;
            int l = it->fr;
            int r = it->sc;
            curw-= (ps[r]-ps[l-1])*(ps[r]-ps[l-1]+1)/2; curw%= mod;
            st.erase(it);
            if(i != l) {
                st.insert(mp(l,i-1));
                curw+= (ps[i-1]-ps[l-1])*(ps[i-1]-ps[l-1]+1)/2; curw%= mod;
            }
            if(i != r) {
                st.insert(mp(i+1,r));
                curw+= (ps[r]-ps[i])*(ps[r]-ps[i]+1)/2; curw%= mod;
            }
        }
    }

    ans = (ans+mod)%mod;
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 16 ms 3652 KB Output is correct
4 Correct 38 ms 6216 KB Output is correct
5 Correct 34 ms 6564 KB Output is correct
6 Correct 29 ms 5904 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 984 KB Output is correct
3 Correct 13 ms 3412 KB Output is correct
4 Correct 25 ms 6204 KB Output is correct
5 Correct 32 ms 6440 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 904 KB Output is correct
4 Correct 12 ms 3412 KB Output is correct
5 Correct 25 ms 6216 KB Output is correct
6 Correct 32 ms 6420 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 5 ms 1836 KB Output is correct
9 Correct 22 ms 5200 KB Output is correct
10 Correct 53 ms 15432 KB Output is correct
11 Correct 53 ms 15524 KB Output is correct
12 Correct 1 ms 328 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 380 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 416 KB Output is correct
16 Correct 1 ms 340 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 18 ms 3604 KB Output is correct
12 Correct 39 ms 6196 KB Output is correct
13 Correct 33 ms 6560 KB Output is correct
14 Correct 26 ms 5864 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 3 ms 900 KB Output is correct
17 Correct 13 ms 3412 KB Output is correct
18 Correct 26 ms 6312 KB Output is correct
19 Correct 28 ms 6320 KB Output is correct
20 Correct 1 ms 464 KB Output is correct
21 Correct 5 ms 1748 KB Output is correct
22 Correct 21 ms 5288 KB Output is correct
23 Correct 60 ms 15404 KB Output is correct
24 Correct 54 ms 15440 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 464 KB Output is correct
30 Correct 9 ms 1876 KB Output is correct
31 Correct 8 ms 2004 KB Output is correct
32 Correct 28 ms 3668 KB Output is correct
33 Correct 57 ms 8624 KB Output is correct
34 Correct 129 ms 16316 KB Output is correct
35 Correct 57 ms 6892 KB Output is correct
36 Correct 138 ms 17044 KB Output is correct
37 Correct 111 ms 12900 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 91 ms 10396 KB Output is correct
40 Correct 88 ms 15308 KB Output is correct
41 Correct 57 ms 15460 KB Output is correct
42 Correct 56 ms 15540 KB Output is correct