Submission #572517

#	Time	Username	Problem	Language	Result	Execution time	Memory
572517		teki	Fancy Fence (CEOI20_fancyfence)	C++11	100 / 100	43 ms	7536 KiB

fancyfence

#include <bits/stdc++.h>

typedef long long ll;

#define pb push_back
#define MS(x,y) memset((x),(y),sizeof((x)))
#define MN 1000000007

using namespace std;

ll n, curr = 0, res = 0, x = 0;
ll h[100001],w[100001];

ll calcZbir(ll w) {
    w %= MN;
    return (w*(w-1)/2)%MN;
}

int main()
{
    #if LOCAL_DEBUG
        fstream cin("in.txt");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for (int i = 0; i<n; i++) cin>>h[i];
    for (int i = 0; i<n; i++) cin>>w[i];
    n++;

    stack<pair<ll,ll>> st;
    st.push({0,-1});

    for (int i = 0; i<n; i++) {
        vector<pair<ll,ll>> v2;

        while(st.top().second >= h[i]) {
            v2.pb(st.top());
            st.pop();
            v2.back().first -= st.top().first;
        }

        for (int j = 1; j<v2.size(); j++) v2[j].first += v2[j-1].first;

        v2.pb({MN+1,h[i]});

        for (int j = 0; j<v2.size()-1; j++) {
            ll temp = v2[j].second-v2[j+1].second;

            res += (calcZbir(v2[j].first+1))*(temp*v2[j+1].second%MN+calcZbir(temp+1));
            res %= MN;
        }

        x += w[i];
        st.push({x,h[i]});
    }

    cout<<res<<endl;

    return 0;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:46:26: 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]
   46 |         for (int j = 1; j<v2.size(); j++) v2[j].first += v2[j-1].first;
      |                         ~^~~~~~~~~~
fancyfence.cpp:50:26: 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]
   50 |         for (int j = 0; j<v2.size()-1; j++) {
      |                         ~^~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27