oj.uz

Submission #558354

# Submission time Handle Problem Language Result Execution time Memory
558354 2022-05-07T07:13:56 Z Stickfish Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 2 ms 340 KB 
#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

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 / 0.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 0 ms 212 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 308 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 1 ms 212 KB Output is correct
2 Incorrect 2 ms 324 KB Output isn't correct
3 Halted 0 ms 0 KB -