oj.uz

Submission #881421

# Submission time Handle Problem Language Result Execution time Memory
881421 2023-12-01T08:42:34 Z Shayan86 Fancy Fence (CEOI20_fancyfence) C++14
12 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

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

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 1e5 + 50;
const ll Mod = 1e9 + 7;

ll n, h[N], w[N], pre[N], L[N], R[N], inv2;

vector<int> jahat, vv;

ll power(ll a, ll b, ll md = Mod){
    ll ans = 1;
    for(; b; b /= 2, a = a * a % md){
        if(b % 2) ans = ans * a % md;
    }
    return ans;
}

ll c2(ll x){
    return x * (x-1) % Mod * inv2 % Mod;
}

bool cmp(int i, int j){
    return (Mp(h[i], i) < Mp(h[j], j));
}

int main(){
    fast_io;

    inv2 = power(2, Mod-2);

    cin >> n;

    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++){
        cin >> w[i]; pre[i] = pre[i-1] + w[i];
    }

    vector<int> vec; vec.pb(0);
    for(int i = 1; i <= n; i++){
        while(h[vec.back()] >= h[i]) vec.pop_back();
        L[i] = vec.back(); vec.pb(i);
    }

    vec.clear(); vec.pb(n+1);
    for(int i = n; i > 0; i--){
        while(h[vec.back()] >= h[i]) vec.pop_back();
        R[i] = vec.back(); vec.pb(i);
    }

    for(int i = 1; i <= n; i++) jahat.pb(i);
    sort(all(jahat), cmp);

    vv.pb(jahat[0]);
    for(int i = 1; i < n; i++) if(h[jahat[i-1]] != h[jahat[i]] || L[jahat[i-1]] != L[jahat[i]]) vv.pb(jahat[i]);

    ll res = 0;
    for(int i: vv){
        ll mx = max(h[L[i]], h[R[i]]);
        ll th1 = (h[i] - mx) * mx + (h[i] - mx) + c2(h[i] - mx); th1 %= Mod;
        ll th2 = c2(pre[R[i]-1] - pre[L[i]]) + pre[R[i]-1] - pre[L[i]]; th2 %= Mod;
        res = (res + th1 * th2) % Mod;
    }

    cout << res;

}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 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 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# 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 -

Subtask #7
0 / 27.0

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