oj.uz

Submission #1046176

# Submission time Handle Problem Language Result Execution time Memory
1046176 2024-08-06T11:08:29 Z ByeWorld Fancy Fence (CEOI20_fancyfence) C++14
100 / 100
 64 ms 24360 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
typedef pair<ld,ld> pll;
const int MAXN = 3e5+15;
const int INF = 3e18+10;
const int MX = 2e18;
const int MOD = 1e9+7;
void chmn(int &a, int b){ a = min(a, b); }
void chsum(int &a, int b){ a%=MOD; b%=MOD; a = (a+b)%MOD; }
void chmul(int &a, int b){ a%=MOD; b%=MOD; a = (a*b)%MOD; }
int mul(int a, int b){ a%=MOD; b%=MOD; return (a*b)%MOD; }
int sum(int a, int b){ a%=MOD; b%=MOD; return (a+b)%MOD; }
int expo(int a, int b){
    if(b==0) return 1;
    int te = expo(a, b/2); te = mul(te, te);
    return (b%2 ? mul(te, a) : te);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
int h[MAXN], w[MAXN], pr[MAXN];
int two;

struct seg {
    pii st[4*MAXN];
    void bd(int id,int l, int r){
        if(l==r){ st[id] = pii(h[l], l); return; }
        bd(lf, l, md); bd(rg, md+1, r);
        st[id] = min(st[lf], st[rg]);
    }
    pii que(int id, int l, int r, int x, int y){
        if(x<=l && r<=y) return st[id];
        if(r<x || y<l) return pii(INF, INF);
        return min(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
    }
} A;
int get(int x, int y){
    return pr[y]-pr[x-1];
}
int CNT(int x, int y, int h){ // x kiri kanan, y atas bawah, h blocks di bwh
    int X = mul(mul(x, x+1), two);
    int Y = mul(mul(y, y+1), two);
    chsum(Y, mul(h, y));
    return mul(X, Y);
}

int ans;
void solve(int l, int r, int las){ // las height
    if(l>r) return;
    int mn = A.que(1,1,n,l,r).se, val = A.que(1,1,n,l,r).fi;
    chsum(ans, CNT(get(l, r), val-las, las));

    solve(l, mn-1, val); solve(mn+1, r, val);
}

signed main(){
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    two = expo(2, MOD-2);
    for(int i=1; i<=n; i++) cin >> h[i];
    A.bd(1, 1, n);
    for(int i=1; i<=n; i++){ cin >> w[i]; pr[i] = pr[i-1]+w[i]; }

    solve(1, n, 0);
    cout << ans << '\n';
}
/*
2
2 2
2 2
//30
*/

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 20 ms 9308 KB Output is correct
4 Correct 53 ms 11876 KB Output is correct
5 Correct 49 ms 11992 KB Output is correct
6 Correct 41 ms 11864 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 6 ms 8796 KB Output is correct
3 Correct 28 ms 8792 KB Output is correct
4 Correct 49 ms 10844 KB Output is correct
5 Correct 64 ms 10840 KB Output is correct
6 Correct 1 ms 6488 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 6 ms 9008 KB Output is correct
4 Correct 25 ms 9560 KB Output is correct
5 Correct 50 ms 12712 KB Output is correct
6 Correct 53 ms 12716 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 5 ms 8796 KB Output is correct
9 Correct 25 ms 9692 KB Output is correct
10 Correct 48 ms 12628 KB Output is correct
11 Correct 50 ms 12584 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6744 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 20 ms 9400 KB Output is correct
12 Correct 42 ms 11860 KB Output is correct
13 Correct 53 ms 11864 KB Output is correct
14 Correct 48 ms 11856 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 6 ms 8904 KB Output is correct
17 Correct 25 ms 9564 KB Output is correct
18 Correct 52 ms 12788 KB Output is correct
19 Correct 51 ms 12892 KB Output is correct
20 Correct 2 ms 6488 KB Output is correct
21 Correct 6 ms 8792 KB Output is correct
22 Correct 26 ms 9688 KB Output is correct
23 Correct 48 ms 12488 KB Output is correct
24 Correct 50 ms 12588 KB Output is correct
25 Correct 1 ms 6488 KB Output is correct
26 Correct 1 ms 6488 KB Output is correct
27 Correct 1 ms 6660 KB Output is correct
28 Correct 1 ms 6492 KB Output is correct
29 Correct 1 ms 6492 KB Output is correct
30 Correct 6 ms 9008 KB Output is correct
31 Correct 6 ms 9004 KB Output is correct
32 Correct 25 ms 9652 KB Output is correct
33 Correct 33 ms 9780 KB Output is correct
34 Correct 52 ms 12608 KB Output is correct
35 Correct 52 ms 12372 KB Output is correct
36 Correct 57 ms 12624 KB Output is correct
37 Correct 63 ms 12884 KB Output is correct
38 Correct 1 ms 6492 KB Output is correct
39 Correct 54 ms 12620 KB Output is correct
40 Correct 58 ms 12896 KB Output is correct
41 Correct 58 ms 14932 KB Output is correct
42 Correct 57 ms 24360 KB Output is correct