Submission #558354

#	Time	Username	Problem	Language	Result	Execution time	Memory
558354		Stickfish	Fancy Fence (CEOI20_fancyfence)	C++17	0 / 100	2 ms	340 KiB

fancyfence

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

const int MAXN = 1e5 + 123;
const ll INF = 1e18 + 132;
const ll MOD = 1000000007;
pair<ll, ll> rsz[MAXN];

ll choose_2(ll x) {
    x %= MOD;
    return x * (x - 1) / 2 % MOD;
}

signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> rsz[i].first;
    for (int i = 0; i < n; ++i)
        cin >> rsz[i].second;
    ++n;
    ll ans = 0;
    vector<pair<ll, ll>> stck;
    stck.push_back({0, -1});
    ll curx = 0;
    for (int i = 0; i < n; ++i) {
        vector<pair<ll, ll>> rdel;
        while (stck.back().second >= rsz[i].second) {
            rdel.push_back(stck.back());
            stck.pop_back();
            rdel.back().first -= stck.back().first;
        }
        for (int j = 1; j < rdel.size(); ++j)
            rdel[j].first += rdel[j - 1].first;
        rdel.push_back({INF, rsz[i].second});
        for (int j = 0; j + 1 < rdel.size(); ++j) {
            ll choose_xs = choose_2(rdel[j].first + 1);
            ll upy = rdel[j].second - rdel[j + 1].second;
            ll choose_ys = upy * rdel[j + 1].second % MOD + choose_2(upy + 1);
            ans += choose_xs * choose_ys;
            ans %= MOD;
        }


        curx += rsz[i].first;
        stck.push_back({curx, rsz[i].second});
    }
    cout << ans << endl;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:35:27: 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]
   35 |         for (int j = 1; j < rdel.size(); ++j)
      |                         ~~^~~~~~~~~~~~~
fancyfence.cpp:38:31: 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]
   38 |         for (int j = 0; j + 1 < rdel.size(); ++j) {
      |                         ~~~~~~^~~~~~~~~~~~~

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