Submission #1279218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279218		haithamcoder	Fancy Fence (CEOI20_fancyfence)	C++20	0 / 100	1108 ms	292692 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
const ll inv = (MOD + 1) / 2;


#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);

ll nc2(ll n) { return ((((n % MOD) * ((n - 1) % MOD)) % MOD)* inv) % MOD; }

void add(ll& a, ll b) {
    a = (a + b) % MOD;
}

void sub(ll& a, ll b) {
    a = (a - b + MOD) % MOD;
}

int main() {
    Algerian OI

    freopen("input13.txt", "r", stdin);
    freopen("hehe.txt", "w", stdout);

    ll n;
    cin >> n;

    map<ll, vector<ll>> heights;
    vector<ll> h(n), w(n), p(n);
    ll r = 0;

    for (ll i = 0; i < n; i++) cin >> h[i];
    for (ll i = 0; i < n; i++) { cin >> w[i]; r += w[i], p[i] = r;}

    for (ll i = 0; i < n; i++) {
        heights[h[i]].push_back(i);
    }

    set<ll> points = {-1, n};
    // multiset<ll> len = {p[n - 1]};
    ll cur_segments = nc2(p[n - 1]);
    ll res = 0;

    for (ll i = 0; i < n; i++) add(res, (nc2(h[i] + 1) * w[i]) % MOD);

    // dbg(res);

    ll pre = 0;


    for (auto&  [u, v] : heights) {
        // dbg(u);
        ll delta = u - pre;
        add(res, cur_segments * (nc2(delta + 1) + (delta * pre % MOD)) % MOD);
        pre = u;


        for (auto& pt : v) {
            auto it = points.lower_bound(pt);
            ll r = *it, l = *prev(it);
            
            ll length = p[r - 1] - (l >= 0 ? p[l] : 0);
            
            // len.erase(len.find(length));
            // dbg("here");

            sub(cur_segments, nc2(length));

            points.insert(pt);

            ll new_len[] = {(pt > 0 ? p[pt - 1] : 0) - (l >= 0 ? p[l] : 0), p[r - 1] - p[pt]};
            // len.insert(new_len[0]);
            // len.insert(new_len[1]);

            add(cur_segments, nc2(new_len[0]));
            add(cur_segments, nc2(new_len[1]));
        }
    }

    cout << res << "\n";

    return 0;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen("input13.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen("hehe.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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