oj.uz

Submission #528284

# Submission time Handle Problem Language Result Execution time Memory
528284 2022-02-19T19:20:35 Z Olympia Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 1000 ms 3144 KB 
#include <cmath>
#include <cassert>
#include <iostream>
#include <set>
#include <climits>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <type_traits>
#include <string>
#include <queue>
#include <map>
#include <stack>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("Ofast")
using namespace std;
int M = 1e9 + 7;
struct modint {
    modint() : n(0) {}

    template<class T>
    modint(T n) {
        n %= M;
        if (n < 0) n += M;
        this->n = n;
    }

    modint &operator+=(const modint &r) {
        n += r.n;
        if (n >= M) n -= M;
        return *this;
    }

    modint &operator-=(const modint &r) {
        n -= r.n;
        if (n < 0) n += M;
        return *this;
    }

    modint &operator*=(const modint &r) {
        n = (int) ((long long) n * r.n % M);
        return *this;
    }

    modint &operator--() {
        if (--n == -1) n = M - 1;
        return *this;
    }

    modint &operator++() {
        if (++n == M) n = 0;
        return *this;
    }

    modint operator--(int) {
        modint t = *this;
        --*this;
        return t;
    }

    modint operator++(int) {
        modint t = *this;
        ++*this;
        return t;
    }

    modint operator-() const { return 0 - *this; }

    modint operator+() const { return *this; }

    modint pow(long long k = M - 2) const {
        modint f = *this, p = 1;
        while (k > 0) {
            if (k % 2 == 1) f *= p;
            p *= p, k /= 2;
        }
        return f;
    }

    int mod() const { return M; }

    friend modint operator+(modint l, const modint &r) { return l += r; }

    friend modint operator-(modint l, const modint &r) { return l -= r; }

    friend modint operator*(modint l, const modint &r) { return l *= r; }

    friend bool operator==(const modint &l, const modint &r) { return l.n == r.n; }

    friend bool operator!=(const modint &l, const modint &r) { return l.n != r.n; }

    friend ostream &operator<<(ostream &out, const modint &r) { return out << r.n; }

    int n;
};
modint c2 (modint x) {
    int64_t n = x.n;
    return (n * (n + 1)/2) % M;
}
const int MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<modint> h(N), w(N);
    vector<pair<modint, modint>> grid(N);
    map<int,vector<int>> myMap;
    for (int i = 0; i < N; i++) {
        cin >> h[i].n;
        myMap[h[i].n].push_back(i);
    }
    vector<modint> pref = {0};
    for (int i = 0; i < N; i++) {
        cin >> w[i].n;
        pref.push_back(pref.back() + w[i]);
    }
    for (int i = 0; i < N; i++) {
        grid[i] = make_pair(w[i], h[i]);
    }
    modint ans = 0;
    for (auto& p: myMap) {
        int x = p.first;
        for (int i: p.second) {
            if (h[i] == x) {
                int l = i;
                while (l >= 1) {
                    if (h[l - 1].n >= x) {
                        l--;
                    } else {
                        break;
                    }
                }
                int r = i;
                while (r < N - 1) {
                    if (h[r + 1].n > x) {
                        r++;
                    } else {
                        break;
                    }
                }
                modint sum = (pref[i] - pref[l]) * (pref[r + 1] - pref[i + 1]);
                sum += (pref[r + 1] - pref[l] - w[i]) * w[i];
                ans += sum* c2(x);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        ans += c2(grid[i].first) * c2(grid[i].second);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message

fancyfence.cpp:16: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   16 | #pragma GCC optimization ("O3")
      | 
fancyfence.cpp:17: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   17 | #pragma GCC optimization ("unroll-loops")
      | 
fancyfence.cpp:18: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   18 | #pragma GCC optimization ("Ofast")
      |

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 196 ms 1720 KB Output is correct
4 Execution timed out 1092 ms 3144 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 22 ms 588 KB Output is correct
3 Correct 428 ms 1616 KB Output is correct
4 Execution timed out 1078 ms 2952 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 21 ms 620 KB Output is correct
4 Correct 445 ms 1688 KB Output is correct
5 Execution timed out 1090 ms 3020 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 202 ms 1700 KB Output is correct
12 Execution timed out 1086 ms 3116 KB Time limit exceeded
13 Halted 0 ms 0 KB -