Submission #413329

#	Time	Username	Problem	Language	Result	Execution time	Memory
413329		Tiago_Marques	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	100 ms	39788 KiB

fancyfence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef priority_queue<ll> pqll;
typedef priority_queue<int> pqi;
typedef set<ll> sll;
typedef set<int> si;
typedef unordered_set<int> usi;
typedef unordered_set<ll> usll;
typedef multiset<ll> msll;
typedef multiset<int> msi;
typedef unordered_multiset<int> umsi;
typedef unordered_multiset<ll> umsll;
typedef map<ll, ll> mll;
typedef map<int, int> mi;
typedef unordered_map<int, int> umi;
typedef unordered_map<ll, ll> umll;
typedef multimap<ll, ll> mmll;
typedef multimap<int, int> mmi;
typedef unordered_multimap<int, int> ummi;
typedef unordered_multimap<ll, ll> ummll;
typedef tree < int ,  null_type ,  less<int> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;

#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define pf push_front
#define mp make_pair
#define fs first
#define sd second
#define all(x) x.begin(), x.end()
#define REP(i, a, b) for (int i=a; i<b; i++)
#define REP_BACK(i, a, b) for (ll i=a-1; i>=b; i--)
#define TRAV(a, v) for(auto a : v)
#define file ifstream cin ("file.in"); ofstream cout ("file.out");

const long long int MOD = 1e9+7;
const long long int INF = 1e18;
const long double EPS = 1e-9;

struct pair_hash
{
    template <class T1, class T2>
    size_t operator() (const pair<T1, T2> &par) const {
        return hash<T1>()(par.first) ^ hash<T2>()(par.second);
    }
};

ll n, x;
ll h[100000], w[100000], sum[100001];
pll sparse_table[100000][20] = {};
ll ans = 0;

void solve (ll menor, ll maior, ll done)
{
    if (maior < menor)
        return;
    ll x = log2(maior-menor+1);
    pll a;
    if (sparse_table[menor][x].fs < sparse_table[maior - ((ll)1<<x) + 1][x].fs)
        a = sparse_table[menor][x];
    else
        a = sparse_table[maior - ((ll)1<<x) + 1][x];
    ll height = (a.fs*(a.fs + 1)/2 - done*(done + 1)/2 + MOD)%MOD;
    ll weight = ((sum[maior+1] - sum[menor])*(sum[maior+1] - sum[menor] + 1)/2)%MOD;
    ans = (ans + height*weight)%MOD;
    if (a.sd != menor)
        solve (menor, a.sd - 1, a.fs);
    if (a.sd != maior)
        solve (a.sd + 1, maior, a.fs);
}

int main()
{
    speed;
    cin >> n;
    REP(i, 0, n)
        cin >> h[i];
    REP(i, 0, n)
        cin >> w[i];
    sum[0] = 0;
    REP(i, 0, n)
        sum[i+1] = (sum[i] + w[i])%MOD;
    for (ll i=n-1; i>=0; i--)
    {
        sparse_table[i][0].fs = h[i];
        sparse_table[i][0].sd = i;
        ll j = 1;
        while (i + ((ll)1<<j) <= n)
        {
            if (sparse_table[i][j-1].fs > sparse_table[i + ((ll)1<<(j-1))][j-1].fs)
                sparse_table[i][j] = sparse_table[i + ((ll)1<<(j-1))][j-1];
            else
                sparse_table[i][j] = sparse_table[i][j-1];
            j ++;
        }
    }
    solve (0, n-1, 0);
    cout << ans << endl;
    return 0;
}

• 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