oj.uz

Submission #923496

# Submission time Handle Problem Language Result Execution time Memory
923496 2024-02-07T10:48:05 Z Art_ogo Fancy Fence (CEOI20_fancyfence) C++17
55 / 100
 60 ms 8236 KB 
#include <bits/stdc++.h>

#define ve vector
#define ld long double
#define ll long long
#define all(x) x.begin(), x.end()
#define fi first
#define se second

using namespace std;
using namespace chrono;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#pragma GCC optimize("Ofast")

const int MAXN = 1e5+10;
const ll mod = 1e9+7;

struct rect{
    ll h, w, id;
};

inline bool comp(const rect& r1, const rect& r2){
    return r1.h < r2.h;
}

rect v[MAXN];
ll pref[MAXN];

int n;

ll binpow(ll a, ll n){
    if(n == 0)
        return 1;
    if(n & 1)
        return (a*binpow(a, n - 1))%mod;
    ll t = binpow(a, n / 2);
    return (t*t) % mod;
}

ll f(ll w){
    ll csum = (w*(w - 1)+mod)%mod;
    csum = (csum*binpow(2, mod - 2)) % mod;
    csum = (csum + w) % mod;
    return csum;
}

void solve(){
    cin >> n; 
    set<int> del;
    for(int i = 1; i <= n; i++)
        cin >> v[i].h;
    for(int i = 1; i <= n; i++)
        cin >> v[i].w;
    for(int i = 1; i <= n; i++)
        v[i].id = i;
    for(int i = 1; i <= n; i++)
        pref[i] = (pref[i - 1] + v[i].w) % mod;
    sort(v + 1, v + 1 + n, comp);
    ll res = 0;
    ll w = (pref[n] - pref[0] + mod) % mod;
    ll csum = f(w);
    for(int i = 1; i <= n; i++){
        auto it = del.lower_bound(v[i].id);
        ll l, r;
        if(it == del.end())
            r = n;
        else r = *it - 1;
        if(it == del.begin())
            l = 0;
        else
            l = *prev(it);
        
        ll ph;
        if(i == 1)
            ph = 0;
        else ph = v[i - 1].h;
        ll sum = ((ph + 1)+v[i].h) % mod;
        sum = (sum*(v[i].h - ph) + mod)%mod;
        sum = (sum*binpow(2, mod - 2)) % mod;
        ll pr = (csum*sum) % mod;
        res = (res + pr) % mod;
        del.insert(v[i].id);
        w = (pref[r] - pref[l] + mod) % mod;
        csum -= f(w);
        w = (pref[v[i].id - 1] - pref[l] + mod) % mod;
        csum += f(w);
        w = (pref[r] - pref[v[i].id] + mod) % mod;
        csum += f(w);
    }
    cout << res;
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T = 1;
    /* cin >> T; */
    while(T--){
        solve();
    }
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 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 2 ms 2392 KB Output is correct

Subtask #3
13.0 / 13.0

# 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 28 ms 4828 KB Output is correct
4 Correct 56 ms 8104 KB Output is correct
5 Correct 58 ms 8088 KB Output is correct
6 Correct 54 ms 8020 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 6 ms 2908 KB Output is correct
3 Correct 29 ms 5032 KB Output is correct
4 Correct 57 ms 8168 KB Output is correct
5 Correct 57 ms 8024 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #5
15.0 / 15.0

# 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 6 ms 2904 KB Output is correct
4 Correct 27 ms 4944 KB Output is correct
5 Correct 56 ms 8236 KB Output is correct
6 Correct 56 ms 8016 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 6 ms 2904 KB Output is correct
9 Correct 29 ms 4956 KB Output is correct
10 Correct 59 ms 8136 KB Output is correct
11 Correct 60 ms 8024 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -