oj.uz

Submission #923485

# Submission time Handle Problem Language Result Execution time Memory
923485 2024-02-07T10:36:54 Z Art_ogo Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 1 ms 348 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{
    int 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;
    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);
    ve<int> add;
    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)*(v[i].h - ph)/2;
        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] - pref[l] + mod) % mod;
        csum += f(w);
        w = (pref[r] - pref[v[i].id + 1] + 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

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

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