oj.uz

Submission #749043

# Submission time Handle Problem Language Result Execution time Memory
749043 2023-05-27T09:25:09 Z bgnbvnbv Fancy Fence (CEOI20_fancyfence) C++14
40 / 100
 39 ms 9084 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll get(ll l,ll r)
{
    if(r<l) return 0;
    ll sum=(r+l);
    ll cnt=(r-l+1);
    if(sum%2==0) sum/=2;
    else cnt/=2;
    sum%=mod;
    cnt%=mod;
    return sum*cnt%mod;
}
ll n,h[maxN];
deque<int> dq;
vector<pli>vec;
ll l[maxN],r[maxN],w[maxN],low[maxN],high[maxN];
void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> h[i];
    for(int i=1;i<=n;i++) cin >> w[i];
    ll last=0;
    for(int i=1;i<=n;i++)
    {
        low[i]=last+1;
        high[i]=last+w[i];
        last+=w[i];
    }
    low[n+1]=last+1;
    high[0]=0;
    for(int i=1;i<=n;i++)
    {
        while(!dq.empty()&&h[i]<=h[dq.back()]) dq.pop_back();
        if(dq.size()) l[i]=dq.back();
        else l[i]=0;
        vec.emplace_back(h[i],i);
        dq.pb(i);
    }
    dq.clear();
    ll ans=0;
    ll sum=0;
    for(int i=n;i>=1;i--)
    {
        while(!dq.empty()&&h[i]<h[dq.back()]) dq.pop_back();
        if(dq.size()) r[i]=dq.back();
        else r[i]=n+1;
        ans+=h[i]*((high[i]-high[l[i]])%mod)%mod*((low[r[i]]-high[i])%mod)%mod;
        ans+=h[i]*get(low[i],high[i]-1)%mod-h[i]*(high[l[i]]%mod)%mod*((high[i]-low[i])%mod)%mod;
        ans%=mod;
        if(ans<0) ans+=mod;
        sum+=((high[i]-high[l[i]])%mod)*((low[r[i]]-high[i])%mod)%mod;
        sum+=get(low[i],high[i]-1)-high[l[i]]%mod*((high[i]-low[i])%mod)%mod;
        sum%=mod;
        if(sum<0) sum+=mod;
        dq.pb(i);
    }
    ll vc=ans;
    sort(vec.begin(),vec.end());
    ll cur=0;
    for(int i=0;i<vec.size();i++)
    {
        ans+=(vec[i].first-cur)*vc%mod-get(1,vec[i].first-cur)*sum%mod;
        vc-=(vec[i].fi-cur)*sum%mod;
        ans=ans%mod;
        if(ans<0) ans+=mod;
        vc%=mod;
        if(vc<0) vc+=mod;
        ll x=vec[i].se;
        sum-=((high[x]-high[l[x]])%mod)*((low[r[x]]-high[x])%mod)%mod;
        sum-=get(low[x],high[x]-1)-high[l[x]]%mod*((high[i]-low[i])%mod)%mod;
        sum%=mod;
        if(sum<0) sum+=mod;
        cur=vec[i].fi;
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

fancyfence.cpp: In function 'void solve()':
fancyfence.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i=0;i<vec.size();i++)
      |                 ~^~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 240 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 18 ms 4196 KB Output is correct
4 Correct 39 ms 8136 KB Output is correct
5 Correct 32 ms 7824 KB Output is correct
6 Correct 31 ms 7816 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 4 ms 1240 KB Output is correct
3 Correct 18 ms 4660 KB Output is correct
4 Correct 36 ms 8908 KB Output is correct
5 Correct 36 ms 9072 KB Output is correct
6 Correct 0 ms 340 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 4 ms 1240 KB Output is correct
4 Correct 16 ms 4756 KB Output is correct
5 Correct 32 ms 8908 KB Output is correct
6 Correct 35 ms 9084 KB Output is correct
7 Incorrect 1 ms 468 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

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