Submission #445572

#	Time	Username	Problem	Language	Result	Execution time	Memory
445572		hgmhc	Fancy Fence (CEOI20_fancyfence)	C++17	45 / 100	1093 ms	6296 KiB

fancyfence

#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define PER(i,a,b) for (auto i = (b); i >= (a); --i)
#define log2(x) (31-__builtin_clz(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define PB push_back
#define FI first
#define SE second
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define debug(x) cout << #x << " is " << x << el
#define el '\n'
using namespace std; using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>;
void solution(); int main() {ios::sync_with_stdio(0); cin.tie(0); solution();}
const int N = 100003; const ll MOD = 1e9+7;
int n; ll h[N], w[N], prefix[N];
inline ll bin2(ll x) {return (x*(x-1)/2)%MOD;}
 
int tree[N<<2];
void update(int t, int x, iii node = {1,1,n}) {
    auto [k,l,r] = node;
    if (t < l || r < t) return;
    if (l == r) {tree[k] = x; return;}
    int m = (l+r)>>1;
    update(t,x,{k<<1,l,m}); update(t,x,{(k<<1)|1,m+1,r});
    tree[k] = min(tree[k<<1], tree[(k<<1)|1]);
}
auto query(ii range, iii node = {1,1,n}) {
    auto [s,e] = range; auto [k,l,r] = node;
    if (e < l || r < s) return tree[0];
    if (s <= l && r <= e) return tree[k];
    int m = (l+r)>>1;
    return min(query(range,{k<<1,l,m}), query(range,{(k<<1)|1,m+1,r}));
}
 
bool input() {
    cin >> n;
    fill(tree,tree+(N<<2),1000000003);
    cin >> h[1]; update(1,h[1]);
    int v = h[1]; bool allsame = true;
    REP(i,2,n) {
        cin >> h[i];
        if (h[i] != v) allsame = false;
        update(i,h[i]);
    }
    REP(i,1,n) {cin >> w[i]; prefix[i] = (prefix[i-1]+w[i])%MOD;}
    return allsame;
}
void task1() {
    ll ans = 0;
    REP(i,1,n) {
        ans += (bin2(h[i]+1)*bin2(w[i]+1))%MOD;
        ans %= MOD;
    }
    REP(i,1,n) REP(j,i+1,n) {
        ans += (bin2(query({i,j})+1)*((w[i]*w[j])%MOD))%MOD;
        ans %= MOD;
    }
    cout << ans;
} void task2() {
    cout << (bin2(h[1]+1)*bin2(prefix[n]+1))%MOD;
}

void solution() {
    if (input()) task2();
    else task1();
}

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