oj.uz

Submission #887293

# Submission time Handle Problem Language Result Execution time Memory
887293 2023-12-14T08:28:13 Z fanwen Fancy Fence (CEOI20_fancyfence) C++17
100 / 100
 36 ms 19544 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;

template <int Mod>
struct Modular {
private :
    int val;
    static int inverse(int a, int b) {
        a %= b;
        assert(a);
        if(a == 1) return 1;
        return int(b - (long long) inverse(b, a) * (long long) b / a);
    }
public :
    Modular(long long x = 0) : val(x % Mod) { if(val < 0) val += Mod; }

    friend bool operator == (const Modular &a, const Modular &b) { return a.val == b.val; }
    friend bool operator != (const Modular &a, const Modular &b) { return a.val != b.val; }

    Modular& operator = (const long long &x) { val = x % Mod; if(val < 0) val += Mod; return *this; }
    Modular& operator = (const Modular &x) { val = x.val; return *this; }

    friend istream & operator >> (istream &in, Modular &a) { long long x; in >> x; a = Modular(x); return in; }
    friend ostream & operator << (ostream &out, const Modular &a) { return out << a.val; }

    explicit operator int() const { return val; }
    explicit operator bool() const { return val > 0; }

    Modular inv() const {
        Modular res;
        res.val = inverse(val, Mod);
        return res;
    }

    Modular operator ++() { (*this) += 1; return *this; }
    Modular operator --() { (*this) -= 1; return *this; }
    Modular operator ++(int) { (*this) += 1; return *this - 1; }
    Modular operator --(int) { (*this) -= 1; return *this + 1; }

    Modular operator + () const { return *this; }
    Modular operator - () const {
        Modular res;
        res.val = (val ? Mod - val : 0);
        return res;
    }

    Modular& operator += (const Modular &a) {
        val += a.val;
        if(val >= Mod) val -= Mod;
        return *this;
    }
    Modular& operator -= (const Modular &a) {
        val -= a.val;
        if(val < 0) val += Mod;
        return *this;
    }
    Modular& operator *= (const Modular &a) {
        val = 1LL * val * a.val % Mod;
        return *this;
    }
    Modular& operator /= (const Modular &a) {
        (*this) *= a.inv();
        return *this;
    }
    friend Modular operator + (const Modular &a, const Modular &b) { return Modular(a) += b; }
    friend Modular operator - (const Modular &a, const Modular &b) { return Modular(a) -= b; }
    friend Modular operator * (const Modular &a, const Modular &b) { return Modular(a) *= b; }
    friend Modular operator / (const Modular &a, const Modular &b) { return Modular(a) /= b; }
};

// const int Mod = 998244353;
// const int Mod = 1e9 + 9; // 1000000009
const int Mod = 1e9 + 7; // 1000000007

using Modint = Modular <Mod>;

template <class T> T pow(T a, long long b) {
    T ans = 1, mul = a;
    for (; b; b >>= 1) {
        if(b & 1LL) ans *= mul;
        mul *= mul;
    }
    return ans;
}

template<class T, T (*merge) (T, T)>
struct sparse_table {
    vector <vector <T>> q;
    int n;

    sparse_table() {}
    sparse_table(const vector <T> &v) : n((int) v.size()) {
        q.push_back(v);
        for (int k = 1; (1 << k) <= n; ++k) {
            q.emplace_back(n - (1 << k) + 1);
            for (int i = 0; i + (1 << k) <= n; ++i) {
                q[k][i] = merge(q[k - 1][i], q[k - 1][i + (1 << (k - 1))]);
            }
        }
    }

    T get(int l, int r) {
        assert(0 <= l && l <= r && r < n);
        int k = 31 - __builtin_clz(r - l + 1);
        return merge(q[k][l], q[k][r - (1 << k) + 1]);
    }
};

const int MAX = 1e5 + 5;

int n;
pair <int, int> a[MAX];

Modint get(int h, int w) {
    return Modint(h) * Modint(h + 1) * Modint(w) * Modint(w + 1) / 4;
}

int merge(int i, int j) {
    return a[i].fi < a[j].fi ? i : j;
}

Modint pref[MAX];

void you_make_it(void) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].fi;
    for (int i = 1; i <= n; ++i) cin >> a[i].se;
    vector <int> id(n + 1);
    iota(id.begin(), id.end(), 0);
    sparse_table <int, merge> rmq(id);
    for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + a[i].se;

    Modint ans = 0;

    auto get = [&] (int l, int r) -> Modint {
        if(l > r) return 0;
        return pref[r] - pref[l - 1];
    };
    function <void(int, int)> solve = [&] (int l, int r) {
        if(l > r) return;

        int mid = rmq.get(l, r);
        Modint tmp = Modint(a[mid].fi) * Modint(a[mid].fi + 1) / 2;
        ans += tmp * get(l, mid) * get(mid, r);
        ans -= tmp * a[mid].se * a[mid].se;
        ans += tmp * (a[mid].se) * (a[mid].se + 1) / 2;
        solve(l, mid - 1);
        solve(mid + 1, r);
    };

    solve(1, n);

    cout << ans;
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("fancyfence");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:5:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:167:5: note: in expansion of macro 'file'
  167 |     file("fancyfence");
      |     ^~~~
fancyfence.cpp:5:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:167:5: note: in expansion of macro 'file'
  167 |     file("fancyfence");
      |     ^~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 852 KB Output is correct
5 Correct 1 ms 860 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 12 ms 6748 KB Output is correct
4 Correct 24 ms 16732 KB Output is correct
5 Correct 23 ms 12908 KB Output is correct
6 Correct 20 ms 10076 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 4 ms 2396 KB Output is correct
3 Correct 15 ms 8796 KB Output is correct
4 Correct 36 ms 17488 KB Output is correct
5 Correct 29 ms 17512 KB Output is correct
6 Correct 0 ms 856 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 856 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 3 ms 2312 KB Output is correct
4 Correct 14 ms 8948 KB Output is correct
5 Correct 30 ms 17428 KB Output is correct
6 Correct 32 ms 17576 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 3 ms 2396 KB Output is correct
9 Correct 15 ms 8796 KB Output is correct
10 Correct 29 ms 17312 KB Output is correct
11 Correct 28 ms 17492 KB Output is correct
12 Correct 1 ms 856 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 800 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Correct 1 ms 868 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 864 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 0 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 11 ms 6660 KB Output is correct
12 Correct 24 ms 16720 KB Output is correct
13 Correct 23 ms 13056 KB Output is correct
14 Correct 21 ms 10076 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Correct 3 ms 2436 KB Output is correct
17 Correct 14 ms 9820 KB Output is correct
18 Correct 34 ms 19284 KB Output is correct
19 Correct 33 ms 19468 KB Output is correct
20 Correct 1 ms 856 KB Output is correct
21 Correct 3 ms 2396 KB Output is correct
22 Correct 15 ms 10076 KB Output is correct
23 Correct 29 ms 19280 KB Output is correct
24 Correct 32 ms 19492 KB Output is correct
25 Correct 1 ms 856 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 1 ms 860 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 3 ms 1628 KB Output is correct
31 Correct 3 ms 1628 KB Output is correct
32 Correct 12 ms 5212 KB Output is correct
33 Correct 12 ms 5212 KB Output is correct
34 Correct 28 ms 9812 KB Output is correct
35 Correct 24 ms 9816 KB Output is correct
36 Correct 24 ms 10068 KB Output is correct
37 Correct 25 ms 10320 KB Output is correct
38 Correct 1 ms 724 KB Output is correct
39 Correct 24 ms 9960 KB Output is correct
40 Correct 24 ms 10068 KB Output is correct
41 Correct 27 ms 11940 KB Output is correct
42 Correct 29 ms 19544 KB Output is correct