제출 #1219309

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219309		Plot_Twist	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	38 ms	33336 KiB

fancyfence

// Using Cartesian Tree





#include<bits/stdc++.h>
#include<chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using namespace chrono;
#define ll long long
#define vl vector<long long>
#define endl '\n'
const int MOD = 1e9 + 7;
void inputv(vl &v) {for(int i = 0; i < v.size(); i++) cin>>v[i];}
void printv(vl v) {for(auto i : v) cout<<i<<" ";cout<<endl;}

// #ifndef ONLINE_JUDGE
// #include "template.cpp"
// #else
// #define debug(...)
// #define debugArr(...)
// #endif

#define int long long

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;


/* for min  

SparseTable sp(arr, [&](const int& a, const int& b) {
    return min(a,b);
});

*/
template<class T, class Fun = function<T(const T &, const T &)>>
struct SparseTable {
    vector<vector<T>> sp;
    Fun f;
    SparseTable(vector<T> &a, const Fun &g) : f(g) {
        int n = a.size();
        int lg = __lg(n) + 1;
        sp.resize(lg, vector<T>(n));
        for(int i = 0; i < n; i++) sp[0][i] = a[i];
        for(int j = 0; j < (lg-1); j++) {
            for(int i = 0; i < n; i++) {
                if (i + (1 << (j + 1)) > n) break;
                sp[j + 1][i] = f(sp[j][i], sp[j][i + (1 << j)]);
            }
        }
    }
    T get(int l, int r) {
        int k = __lg(r - l);
        return f(sp[k][l], sp[k][r - (1 << k)]);
    }
};


typedef struct Node {
    int h;
    int w;
    int l;
    int r;
    Node* left; 
    Node* right;
}Node;

signed main() {
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt","r",stdin);
    //     freopen("output.txt","w",stdout);
    //     freopen("Error.txt","w",stderr);
    // #endif
    ios::sync_with_stdio(false); cin.tie(NULL);
    // #ifndef ONLINE_JUDGE
    // auto start = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
    // #endif

    int n;
    cin>>n;
    vl ht(n), wt(n);
    inputv(ht);inputv(wt);
    vl ord(n);
    iota(ord.begin(), ord.end(), 0);
    SparseTable st(ord, [&](const int& i, const int& j) {
        return make_pair(ht[i], i) < make_pair(ht[j], j) ? i:j;
    });
    function<Node*(int l, int r)> build = [&](int l, int r)->Node* {
        if(l>r) return nullptr;
        int temp = st.get(l,r+1);
        Node *root = new Node();
        root->h = ht[temp];
        root->w = wt[temp];
        root->left = build(l,temp-1);
        root->right = build(temp+1,r);
        root->l = 0;
        root->r = 0;
        if(root->left) root->l = (((root->left)->l +(root->left)->r)%MOD+ (root->left)->w)%MOD;
        if(root->right) root->r = (((root->right)->l +(root->right)->r)%MOD+ (root->right)->w)%MOD;
        return root;
    };
    Node *root = build(0,n-1);
    int ans = 0;
    function<void(Node*)> solve = [&](Node* curr) {
        if(!curr) return;
        int temp =  (curr->l * ((curr->w + curr->r)%MOD))%MOD;
        temp = (temp + (curr->r * curr->w)%MOD)%MOD;
        temp = (temp + ((curr->w*(curr->w + 1))/2)%MOD)%MOD;
        int temp2 = ((curr->h * (curr->h + 1))/2)%MOD;
        ans = (ans + (temp*temp2)%MOD)%MOD;
        solve(curr->left);
        solve(curr->right);
    };
    solve(root);
    cout<<ans<<endl;




    // #ifndef ONLINE_JUDGE
    // auto stop = duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
    // cerr << "Took " << stop - start << "ms" << endl;
    // #endif
}

• 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