oj.uz

Submission #592133

# Submission time Handle Problem Language Result Execution time Memory
592133 2022-07-08T15:14:55 Z jasmin Fancy Fence (CEOI20_fancyfence) C++14
100 / 100
 206 ms 28972 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int mod=1e9+7;

struct node{
    int left=0;
    int right=0;
    int ans=0;
    int sum=1;
};
node zero={0, 0, 0, 0};

struct segtree{
    vector<node> tree;

    segtree(int n){
        tree.resize(n*4);
        build(0, n, 0);
    };

    node build(int l, int r, int v){
        if(l+1==r){
            tree[v].left=tree[v].right=0;
            tree[v].sum=1;
            tree[v].ans=0;
            return tree[v];
        }
        int m=l+(r-l)/2;
        return tree[v]=merge(build(l, m, v*2+1), build(m, r, v*2+2));
    }

    node merge(node a, node b){
        node ret;
        ret.sum=(a.sum+b.sum)%mod;
        ret.ans=(a.ans+b.ans)%mod;
        ret.left=a.left;
        ret.right=b.right;

        int middle=(a.right+b.left)%mod;
        if(a.left==a.sum){
            middle=0;
            ret.left=(a.sum+b.left)%mod;
        }
        if(b.right==b.sum){
            middle=0;
            ret.right=(a.right+b.sum)%mod;
        }

        ret.ans+=(middle*(middle+1)/2)%mod;
        ret.ans%=mod;

        return ret;
    }

    node update(int l, int r, int v, int x, int val){
        //cout << "update " << l << " " << r << " " << v << " " << x << " " << val << "\n";
        if(x<l || r<=x) {
            //cout << l << " " << r << " " << v << ": " << tree[v].left << " " << tree[v].right << " " << tree[v].sum << " " << tree[v].ans << "\n";
            return tree[v];
        }
        if(l+1==r){
            tree[v].left=val;
            tree[v].right=val;
            tree[v].sum=val;
            tree[v].ans=0;
            //cout << l << " " << r << " " << v << ": " << tree[v].left << " " << tree[v].right << " " << tree[v].sum << " " << tree[v].ans << "\n";
            return tree[v];
        }
        int m=l+(r-l)/2;
        tree[v]=merge(update(l, m, v*2+1, x, val), update(m, r, v*2+2, x, val));
        //cout << l << " " << r << " " << v << ": " << tree[v].left << " " << tree[v].right << " " << tree[v].sum << " " << tree[v].ans << "\n";
        return tree[v];
    }
    node query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return zero;
        if(ql<=l && r<=qr) return tree[v];
        int m=l+(r-l)/2;
        return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }
    
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> h(n);
    map<int,int> ind; int x=1;
    vector<pair<int, vector<int> > >sorted;
    sorted.push_back({0, {}});
    for(int i=0; i<n; i++){
        cin >> h[i];
        if(ind[h[i]]==0){
            sorted.push_back({h[i], {}});
            ind[h[i]]=x;
            x++;
        }
        sorted[ind[h[i]]].second.push_back(i);
    }
    sort(sorted.begin(), sorted.end());
    reverse(sorted.begin(), sorted.end());
    vector<int> w(n);
    for(int i=0; i<n; i++){
        cin >> w[i];
    }

    
    int ans=0;
    segtree seg(n);
    for(int i=0; i<(int)sorted.size()-1; i++){
        int h=sorted[i].first;
        int next=sorted[i+1].first;

        vector<int> ele=sorted[i].second;
        for(auto e: ele){
            seg.update(0, n, 0, e, w[e]);
        }

        node res=seg.query(0, n, 0, 0, n);
        //cout << res.ans << " " << res.left << " " << res.right << "\n";
        int s=res.ans;
        s+= (res.left*(res.left+1)/2)%mod;
        s%=mod;
        if(res.right!=res.sum){
            s+=(res.right*(res.right+1)/2)%mod;
            s%=mod;
        }

        int factor=((h*(h+1))/2 - (next*(next+1))/2)%mod;
        //cout << factor << " " << s << "\n";
        ans+=(s*factor)%mod;
        ans%=mod;
    }

    cout << ans << "\n";
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 42 ms 7900 KB Output is correct
4 Correct 85 ms 16092 KB Output is correct
5 Correct 82 ms 15888 KB Output is correct
6 Correct 78 ms 16044 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 7 ms 1876 KB Output is correct
3 Correct 42 ms 8168 KB Output is correct
4 Correct 92 ms 16132 KB Output is correct
5 Correct 93 ms 16116 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 8 ms 1876 KB Output is correct
4 Correct 47 ms 8244 KB Output is correct
5 Correct 83 ms 16044 KB Output is correct
6 Correct 87 ms 16124 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 11 ms 2892 KB Output is correct
9 Correct 52 ms 10380 KB Output is correct
10 Correct 131 ms 26804 KB Output is correct
11 Correct 141 ms 26932 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #6
18.0 / 18.0

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

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 37 ms 7888 KB Output is correct
12 Correct 82 ms 15972 KB Output is correct
13 Correct 92 ms 15864 KB Output is correct
14 Correct 83 ms 15996 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 7 ms 1876 KB Output is correct
17 Correct 40 ms 8284 KB Output is correct
18 Correct 82 ms 16112 KB Output is correct
19 Correct 87 ms 16356 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 11 ms 3004 KB Output is correct
22 Correct 55 ms 10380 KB Output is correct
23 Correct 165 ms 28764 KB Output is correct
24 Correct 135 ms 28828 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 2 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 14 ms 3020 KB Output is correct
31 Correct 18 ms 3148 KB Output is correct
32 Correct 47 ms 8796 KB Output is correct
33 Correct 87 ms 14612 KB Output is correct
34 Correct 206 ms 28080 KB Output is correct
35 Correct 98 ms 17280 KB Output is correct
36 Correct 205 ms 28788 KB Output is correct
37 Correct 169 ms 24044 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 172 ms 22464 KB Output is correct
40 Correct 167 ms 28668 KB Output is correct
41 Correct 129 ms 28860 KB Output is correct
42 Correct 138 ms 28972 KB Output is correct