oj.uz

Submission #445572

# Submission time Handle Problem Language Result Execution time Memory
445572 2021-07-18T17:31:02 Z hgmhc Fancy Fence (CEOI20_fancyfence) C++17
45 / 100
 1000 ms 6296 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 119 ms 1924 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1860 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 129 ms 1912 KB Output is correct
3 Execution timed out 1087 ms 3512 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 7 ms 2252 KB Output is correct
3 Correct 31 ms 3944 KB Output is correct
4 Correct 60 ms 6144 KB Output is correct
5 Correct 62 ms 6236 KB Output is correct
6 Correct 1 ms 1868 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 7 ms 2252 KB Output is correct
4 Correct 32 ms 3948 KB Output is correct
5 Correct 61 ms 6080 KB Output is correct
6 Correct 67 ms 6296 KB Output is correct
7 Correct 119 ms 1920 KB Output is correct
8 Execution timed out 1080 ms 2252 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 120 ms 1920 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 1 ms 1868 KB Output is correct
5 Correct 1 ms 1868 KB Output is correct
6 Correct 2 ms 1868 KB Output is correct
7 Correct 2 ms 1868 KB Output is correct
8 Correct 118 ms 1916 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 133 ms 1920 KB Output is correct
11 Correct 3 ms 1868 KB Output is correct
12 Correct 28 ms 1868 KB Output is correct
13 Correct 119 ms 1916 KB Output is correct
14 Correct 120 ms 1920 KB Output is correct
15 Correct 118 ms 1868 KB Output is correct
16 Correct 1 ms 1868 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 119 ms 1924 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 121 ms 1868 KB Output is correct
5 Correct 2 ms 1868 KB Output is correct
6 Correct 1 ms 1868 KB Output is correct
7 Correct 1 ms 1868 KB Output is correct
8 Correct 1 ms 1864 KB Output is correct
9 Correct 2 ms 1868 KB Output is correct
10 Correct 118 ms 1868 KB Output is correct
11 Execution timed out 1093 ms 3512 KB Time limit exceeded
12 Halted 0 ms 0 KB -