oj.uz

Submission #1013726

# Submission time Handle Problem Language Result Execution time Memory
1013726 2024-07-04T03:52:12 Z Luvidi Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 1 ms 860 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*(cw+1)/2;
    sum%=MOD;
    s.insert({1,cw});
    for(auto[x,v]:m){
        ll a=x-pr;
        ans+=sum*(a*(a+1)/2+a*pr);
        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});
            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 860 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 1 ms 860 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 860 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -