oj.uz

Submission #1100881

# Submission time Handle Problem Language Result Execution time Memory
1100881 2024-10-15T00:43:00 Z Owstin Fancy Fence (CEOI20_fancyfence) C++17
25 / 100
 23 ms 5484 KB 
#include <bits/stdc++.h>
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define pb push_back
#define all(x) begin(x), end(x)
#define umap unordered_map
#define space " "
#define TEST_CASES int a; cin >> a; for (int i = 0; i < a; i++) {solve(); cout << endl;}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define MOD (ll)(1e9 + 7)
void solve() {
    int b; cin >> b;
    vector<ll> heights(b);
    vector<pair<ll, ll>> width(b);
    for (int i = 0; i < b; i++){
        cin >> heights[i];
    }
    for (int i = 0; i < b; i++){
        ll x; cin >> x;
        if (i == 0){
            width[i] = {0, x - 1};
        }
        else{
            width[i].first = width[i - 1].second + 1;
            width[i].second = width[i].first + x - 1;
        }
    }
    stack<int> s1; stack<int> s2;
    vector<ll> widths(b);
    vector<ll> next(b);
    for (int i = 0; i < b; i++){
        while (!s1.empty() && heights[s1.top()] >= heights[i]){
            if (heights[s1.top()] == heights[i]){
                next[i] = heights[i];
            }
            s1.pop();
        }
        if (!s1.empty()) {
            next[i] = max(next[i], heights[s1.top()]);
        }
        widths[i] += width[i].second - (s1.empty() ? -1 : width[s1.top()].second);
        s1.push(i);
    }
    for (int i = b - 1; i >= 0; i--){
        while (!s2.empty() && heights[s2.top()] >= heights[i]){
            s2.pop();
        }
        if (!s2.empty()) {
            next[i] = max(next[i], heights[s2.top()]);
        }
        widths[i] += (s2.empty() ? width.back().second : width[s2.top()].first - 1) - width[i].second;
        s2.push(i);
    }
    ll res = 0;
    for (int i = 0; i < b; i++){
        widths[i] %= MOD;
        ll tall = (((heights[i] * (heights[i] + 1) / 2) % MOD) -
                ((next[i] % MOD * (next[i] + 1) % MOD / 2) % MOD) + MOD) % MOD;
        ll wide = (widths[i] * (widths[i] + 1) / 2) % MOD;
        res = (res + ((tall * wide) % MOD)) % MOD;
    }
    cout << res;
}
int main() {
    FAST_IO;
    //freopen(R"(C:\Users\caoji\Downloads\prime_subtractorization_input\prime_subtractorization_input.txt)", "r", stdin);
    //freopen("art2.in", "r", stdin);
    //freopen("art2.out", "w", stdout);
    //TEST_CASES;
    solve(); cout << endl;
    /*int a; cin >> a;
    for (int i = 1; i <= a; i++){
        cout << "Case #" << i << ": ";
        solve();
        cout << endl;
    }*/
}

Subtask #1
0.0 / 0.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 11 ms 2912 KB Output is correct
4 Correct 17 ms 5484 KB Output is correct
5 Correct 23 ms 5472 KB Output is correct
6 Correct 16 ms 5476 KB Output is correct

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

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