Submission #855236

#	Time	Username	Problem	Language	Result	Execution time	Memory
855236		anhphant	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	70 ms	14356 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'

ll N, H[500007], W[500007];
const ll mod = 1e9 + 7;

void initialize() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen("FILE.INP", "r")) {
        freopen("FILE.INP", "r", stdin);
        freopen("FILE.OUT", "w", stdout);
    }
    cin >> N;
    for(int i = 1; i <= N; ++i) cin >> H[i];
    for(int i = 1; i <= N; ++i) cin >> W[i];
}

namespace subtask2 {
    ll A[1007][1007];

    void solve() {
        ll lastw = 0;
        for(int i = 1; i <= N; ++i) {
            for(int h = 1; h <= H[i]; ++h) {
                for(int w = lastw + 1; w <= lastw + W[i]; ++w) {
                    A[h][w] = 1;
                }
            }
            lastw += W[i];
        }

        /*for(int i = 1; i <= 50; ++i) {
            for(int j = 1; j <= 50; ++j) {
                cerr << A[i][j];
            }
            cerr << endl;
        }*/

        for(int i = 1; i <= 50; ++i) {
            for(int j = 1; j <= 50; ++j) {
                A[i][j] = A[i][j - 1] + A[i - 1][j] + A[i][j] - A[i - 1][j - 1];
            }
        }

        ll ans = 0;

        for(int i = 1; i <= 50; ++i) {
            for(int j = 1; j <= 50; ++j) {
                for(int k = i; k <= 50; ++k) {
                    for(int l = j; l <= 50; ++l) {
                        ans += (A[k][l] - A[i - 1][l] - A[k][j - 1] + A[i - 1][j - 1])
                                == ((k - i + 1) * (l - j + 1));
                    }
                }
            }
        }

        cout << ans;
    }

    void process() {
        memset(A, 0, sizeof(A));
        solve();
    }
}

namespace subtask3 {
    ll fsum(ll n) {
        ll x1 = n;
        ll x2 = n + 1;
        if (x1 % 2 == 0) x1 /= 2;
        else x2 /= 2;
        x1 %= mod;
        x2 %= mod;
        return (x1 * x2) % mod;
    }

    void solve() {
        vector<ll> split;
        split.push_back(0);
        for(int i = 1; i <= N; ++i) {
            if (H[i] == 1 && split.back() > 0) split.push_back(0);
            if (H[i] == 2) split[split.size() - 1] += W[i];
        }

        ll sum1 = accumulate(W + 1, W + 1 + N, 0LL);
        sum1 = fsum(sum1);
        ll sum2 = 0;
        for(ll c : split) {
            sum2 = (sum2 + fsum(c));
            sum2 %= mod;
        }
        sum2 = (sum2 * 2) % mod;
        cout << (sum1 + sum2) % mod;
    }

    void process() {
        solve();
    }
}

namespace subtask4 {
    ll fsum(ll n) {
        ll x1 = n;
        ll x2 = n + 1;
        if (x1 % 2 == 0) x1 /= 2;
        else x2 /= 2;
        x1 %= mod;
        x2 %= mod;
        return (x1 * x2) % mod;
    }

    void solve() {
        ll sum1 = H[1];
        ll sum2 = accumulate(W + 1, W + 1 + N, 0LL);

        //cerr << sum1 << " " << sum2 << endl;

        cout << (fsum(sum1) * fsum(sum2)) % mod;
    }

    void process() {
        solve();
    }
}

namespace subtask5 {
    ll fsum(ll n) {
        ll x1 = n;
        ll x2 = n + 1;
        if (x1 % 2 == 0) x1 /= 2;
        else x2 /= 2;
        x1 %= mod;
        x2 %= mod;
        return (x1 * x2) % mod;
    }

    void solve() {
        ll sum = accumulate(W + 1, W + 1 + N, 0LL);
        ll ans = 0;

        for(int i = 1; i <= N; ++i) {
            ll total = (fsum(sum) * fsum(H[i])) % mod;
            total -= (fsum(sum) * fsum(H[i - 1])) % mod;
            total = (total + mod) % mod;

            ans = (ans + total) % mod;
            sum -= W[i];
        }

        cout << ans;
    }

    void process() {
        solve();
    }
}

namespace subtask6 {
    ll fsum(ll n) {
        ll x1 = n;
        ll x2 = n + 1;
        if (x1 % 2 == 0) x1 /= 2;
        else x2 /= 2;
        x1 %= mod;
        x2 %= mod;
        return (x1 * x2) % mod;
    }

    ll rmin[1007][1007];

    void rmin_calculate() {
        for(int i = 1; i <= N; ++i) {
            rmin[i][i] = H[i];
            for(int j = i + 1; j <= N; ++j) {
                rmin[i][j] = min(rmin[i][j - 1], H[j]);
            }
        }

        /*for(int i = 1; i <= N; ++i) {
            for(int j = i; j <= N; ++j) {
                cerr << i << " " << j << " " << rmin[i][j] << endl;
            }
        }*/
    }

    void solve() {
        ll ans = 0;

        for(int i = 1; i <= N; ++i) {
            ans += (fsum(H[i]) * fsum(W[i])) % mod;
            ans %= mod;
        }

        for(int i = 1; i <= N; ++i) {
            for(int j = i + 1; j <= N; ++j) {
                ll total = fsum(rmin[i][j]);
                total = (total * W[i]) % mod;
                total = (total * W[j]) % mod;
                ans += total;
                ans %= mod;

                /*cerr << i << " " << j << endl;
                cerr << rmin[i][j] << " " << W[i] << " " << W[j] << " " << total << endl;
                cerr << endl;*/
            }
        }

        cout << ans << endl;
    }

    void process() {
        rmin_calculate();
        solve();
    }
}

namespace subtask7 {
    ll fsum(ll n) {
        ll x1 = n;
        ll x2 = n + 1;
        if (x1 % 2 == 0) x1 /= 2;
        else x2 /= 2;
        x1 %= mod;
        x2 %= mod;
        return (x1 * x2) % mod;
    }

    void Cong(ll& a, ll b) {
        a = ((a % mod) + (b % mod)) % mod;
    }

    ll Tong(ll a, ll b) {
        return ((a % mod) + (b % mod)) % mod;
    }

    void Tru(ll& a, ll b) {
        a = ((a % mod) - (b % mod) + mod) % mod;
    }

    ll Hieu(ll a, ll b) {
        return ((a % mod) - (b % mod) + mod) % mod;
    }

    void Nhan(ll& a, ll b) {
        a = ((a % mod) * (b % mod)) % mod;
    }

    ll Tich(ll a, ll b) {
        return ((a % mod) * (b % mod)) % mod;
    }

    pair<pair<ll, ll>, ll> A[100007];
    set<pair<ll, ll>> se;
    ll PreSumW[100007];
    ll ans = 0;
    ll fsum_segment = 0;

    void pre_process() {
        for(int i = 1; i <= N; ++i) A[i] = {{H[i], W[i]}, i};
        se.insert({1, N});
        for(int i = 1; i <= N; ++i) PreSumW[i] = PreSumW[i - 1] + W[i];

        sort(A + 1, A + 1 + N);

        fsum_segment = fsum(accumulate(W + 1, W + 1 + N, 0LL));
        ans = 0;
    }

    void solve() {
        for(int i = 1; i <= N; ++i) {
            //cerr << "i = " << i << " : " << A[i].first.first << " " << A[i].first.second << " " << A[i].second << endl;
            //for(auto [x1, x2] : se) cerr << x1 << " " << x2 << endl;

            if (A[i].first.first > A[i - 1].first.first) {
                ll tmp = Tich(fsum_segment, fsum(A[i].first.first));
                Tru(tmp, Tich(fsum_segment, fsum(A[i - 1].first.first)));

                //cerr << "get : " << fsum_segment << " " << tmp << endl;

                Cong(ans, tmp);
            }

            pair<ll, ll> s = *prev(se.lower_bound({A[i].second, 9999999999}));
            assert(s.first <= A[i].second && A[i].second <= s.second);

            //cerr << "subtract : " << PreSumW[s.second] - PreSumW[s.first - 1] << endl;
            Tru(fsum_segment, fsum(PreSumW[s.second] - PreSumW[s.first - 1]));
            se.erase(s);

            pair<ll, ll> sleft = {s.first, A[i].second - 1};
            pair<ll, ll> sright = {A[i].second + 1, s.second};

            if (sleft.first <= sleft.second) {
                //cerr << "add : " << PreSumW[sleft.second] - PreSumW[sleft.first - 1] << endl;
                Cong(fsum_segment, fsum(PreSumW[sleft.second] - PreSumW[sleft.first - 1]));
                se.insert(sleft);
            }
            if (sright.first <= sright.second) {
                //cerr << "add : " << PreSumW[sright.second] - PreSumW[sright.first - 1] << endl;
                Cong(fsum_segment, fsum(PreSumW[sright.second] - PreSumW[sright.first - 1]));
                se.insert(sright);
            }

            //cerr << endl;
        }

        cout << ans;
    }

    void process() {
        pre_process();
        solve();
    }
}

int main() {
    initialize();

    ll maxh = *max_element(H + 1, H + 1 + N);
    ll minh = *min_element(H + 1, H + 1 + N);
    ll maxw = *max_element(W + 1, W + 1 + N);
    ll minw = *min_element(W + 1, W + 1 + N);
    //subtask6 :: process();
    subtask7 :: process();
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:323:8: warning: unused variable 'maxh' [-Wunused-variable]
  323 |     ll maxh = *max_element(H + 1, H + 1 + N);
      |        ^~~~
fancyfence.cpp:324:8: warning: unused variable 'minh' [-Wunused-variable]
  324 |     ll minh = *min_element(H + 1, H + 1 + N);
      |        ^~~~
fancyfence.cpp:325:8: warning: unused variable 'maxw' [-Wunused-variable]
  325 |     ll maxw = *max_element(W + 1, W + 1 + N);
      |        ^~~~
fancyfence.cpp:326:8: warning: unused variable 'minw' [-Wunused-variable]
  326 |     ll minw = *min_element(W + 1, W + 1 + N);
      |        ^~~~
fancyfence.cpp: In function 'void initialize()':
fancyfence.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen("FILE.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen("FILE.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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