답안 #1013726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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();
}
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -