oj.uz

Submission #1013727

# Submission time Handle Problem Language Result Execution time Memory
1013727 2024-07-04T03:58:52 Z Luvidi Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 36 ms 14676 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

void solve() {
    int n;
    cin>>n;
    ll h[n],w[n],MOD=1e9+7;
    for(int i=0;i<n;i++)cin>>h[i];
    for(int i=0;i<n;i++)cin>>w[i];
    ll cw=0;
    map<ll,vector<pll>> m;
    for(int i=0;i<n;i++){
        m[h[i]].pb({cw+1,cw+w[i]});
        cw+=w[i];
    }
    set<pll> s;
    ll pr=0,ans=0,sum=cw%MOD*(cw%MOD+1)/2;
    sum%=MOD;
    s.insert({1,cw});
    for(auto[x,v]:m){
        ll a=x-pr;
        ans+=(a*(a+1)/2+a*pr)%MOD*sum;
        ans%=MOD;
        for(auto[l,r]:v){
            auto it=s.upper_bound({l,0});
            it--;
            auto[l2,r2]=*it;
            s.erase(it);
            if(l2<l)s.insert({l2,l-1});
            if(r<r2)s.insert({r+1,r2});
            l%=MOD;
            l2%=MOD;
            r%=MOD;
            r2%=MOD;
            sum-=(r2-l2+1)*(r2-l2+2)/2;
            sum+=(l-l2)*(l-l2+1)/2;
            sum+=(r2-r)*(r2-r+1)/2;
            sum%=MOD;
        }
        pr=x;
    }
    ans+=MOD;
    ans%=MOD;
    cout<<ans<<'\n';
    
}

int main() {   
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 720 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 1248 KB Output is correct
3 Correct 10 ms 3904 KB Output is correct
4 Correct 26 ms 7240 KB Output is correct
5 Correct 21 ms 7124 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 1112 KB Output is correct
4 Correct 11 ms 3776 KB Output is correct
5 Correct 19 ms 7124 KB Output is correct
6 Correct 20 ms 7124 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 4 ms 1752 KB Output is correct
9 Correct 16 ms 5332 KB Output is correct
10 Correct 34 ms 14596 KB Output is correct
11 Correct 36 ms 14676 KB Output is correct
12 Correct 1 ms 456 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 2 ms 748 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1 ms 720 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -