Submission #1301833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301833		guilhermecpp	Fancy Fence (CEOI20_fancyfence)	C++20	12 / 100	1 ms	580 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
 
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); // teste
 
#define int long long
#define fi first
#define se second
#define pb push_back
// #define endl '\n'
 
typedef long long ll;
typedef pair<int,int> pii;
 
const int N = 1e5+5;
const int mod = 1e9+7;
const int inv2 = (mod+1)/2;
const int INF = 1e9+5;

int a[N], b[N];
int accu[N];
int pai[N], lef[N], rig[N];

int Calc(int x, int y)
{
    int ans = 1;
    ans = (ans*x)%mod;
    ans = (ans*(x+1))%mod;
    ans = (ans*inv2)%mod;
    ans = (ans*y)%mod;
    ans = (ans*(y+1))%mod;
    ans = (ans*inv2)%mod;
    return ans;
}

int Solv(int u, int l, int r)
{
    int ans = 0;
    if(!pai[u] || a[pai[u]]!=a[u])
    {
        int x = accu[r]-accu[l-1];
        ans = (Calc(a[u], x)+mod-Calc(a[pai[u]], x))%mod;
    }
    if(lef[u]) ans = (ans+Solv(lef[u], l, u-1))%mod;
    if(rig[u]) ans = (ans+Solv(rig[u], u+1, r))%mod;
    return ans;
}

int32_t main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 1;i <= n;i++) cin >> b[i];
    for(int i = 1;i <= n;i++) accu[i] = accu[i-1]+b[i];

    stack<int> pilha;
    for(int i = 1;i <= n;i++) pai[i] = lef[i] = rig[i] = 0;
    for(int i = 1;i <= n;i++)
    {
        int ult = 0;
        while(!pilha.empty() && a[pilha.top()]>a[i])
        {
            ult = pilha.top();
            pilha.pop();
        }
        if(ult)
        {
            pai[ult] = i;
            lef[i] = ult;
        }
        if(!pilha.empty())
        {
            pai[i] = pilha.top();
            rig[pilha.top()] = i;
        }
        pilha.push(i);
    }

    int root = 1;
    while(pai[root]) root++;
    cout << Solv(root, 1, n) << endl;
    
    return 0;
}

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