Submission #1196117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196117		Zbyszek99	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	27 ms	17480 KiB

fancyfence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

template<typename T>
class SPARSE_TABLE
{
    T** table;
    function<T(T,T)> func;
    int n;
    int* log;
    int max_b = 0;
    public:
    SPARSE_TABLE(int MAXN, function<T(T,T)> func) : func(func)
    {
        log = new int[MAXN+1];
        log[0] = -1;
        for(int i = 1; i <= MAXN; i++)
        {
            log[i] = log[i/2]+1;
        }
        n = 0;
        max_b = -1;
    }
    void setup(int N, T* v)
    {
        for(int i = 0; i <= max_b; i++)
        {
            delete[] table[i];
        }
        delete[] table;
        n = N;
        int max_lg = log[n];
        max_b = max_lg;
        table = new T*[max_lg+1];
        for(int i = 0; i <= max_lg; i++)
        {
            table[i] = new T[n];
        }
        for(int i = 0; i < n; i++)
        {
            table[0][i] = v[i];
        }
        for(int bit = 1; bit <= max_lg; bit++)
        {
            for(int i = 0; i < n; i++)
            {
                if(i + (1 << bit)-1 < n)
                {
                    table[bit][i] = func(table[bit-1][i],table[bit-1][i + (1 << (bit-1))]);
                }
            }
        }
    }
    T query(int l, int r)
    {
        int bit = log[r-l+1];
        return func(table[bit][l],table[bit][r-(1 << bit)+1]);
    }
};

ll H[100001];
ll W[100001];
int pom[100001];

int min_f(int a, int b) {return H[a] < H[b] ? a : b;};

SPARSE_TABLE<int> table(100001,min_f);

ll pref[100001];
ll ans = 0;

void f(int l, int r)
{
    if(l > r) return;
    int min_elm = table.query(l,r);
    ll sides = ((pref[min_elm] - pref[l] + MOD) * (pref[r+1] - pref[min_elm+1] + MOD)) % MOD + (W[min_elm] * (W[min_elm]-1)/2) % MOD + W[min_elm] + (W[min_elm] * (pref[r+1] - pref[l] - W[min_elm] + MOD*5)) % MOD;
    sides %= MOD;
    ll heights = H[min_elm] * (H[min_elm]-1)/2 + H[min_elm];
    heights %= MOD;
    ans += sides * heights;
    ans %= MOD;
    f(l,min_elm-1);
    f(min_elm+1,r);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n;
    cin >> n;
    rep(i,n) cin >> H[i];
    rep(i,n) cin >> W[i];
    rep(i,n) pom[i] = i;
    rep2(i,1,n) pref[i] = (pref[i-1] + W[i-1]) % MOD;
    table.setup(n,pom);
    f(0,n-1);
    cout << ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27