oj.uz

Submission #749014

# Submission time Handle Problem Language Result Execution time Memory
749014 2023-05-27T09:08:01 Z bgnbvnbv Fancy Fence (CEOI20_fancyfence) C++14
12 / 100
 1 ms 340 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;
    return (r+l)*(r-l+1)/2;
}
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]])*(low[r[i]]-high[i]);
        ans+=h[i]*get(low[i],high[i]-1)-h[i]*high[l[i]]*(high[i]-low[i]);
        sum+=(high[i]-high[l[i]])*(low[r[i]]-high[i]);
        sum+=get(low[i],high[i]-1)-high[l[i]]*(high[i]-low[i]);
        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-get(1,vec[i].first-cur)*sum;
        vc-=(vec[i].fi-cur)*sum;
        ll x=vec[i].se;
        sum-=(high[x]-high[l[x]])*(low[r[x]]-high[x]);
        sum-=get(low[x],high[x]-1)-high[l[x]]*(high[x]-low[x]);
        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:61: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]
   61 |     for(int i=0;i<vec.size();i++)
      |                 ~^~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.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 #6
0 / 18.0

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

Subtask #7
0 / 27.0

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