oj.uz

Submission #701517

# Submission time Handle Problem Language Result Execution time Memory
701517 2023-02-21T11:49:33 Z Cyanmond Fancy Fence (CEOI20_fancyfence) C++17
100 / 100
 189 ms 15360 KB 
#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 mod = 1000000007;

i64 add(i64 a, i64 b) {
    return (a + b) % mod;
}
i64 sub(i64 a, i64 b) {
    return (a + mod - b) % mod;
}
i64 mul(i64 a, i64 b) {
    return (a * b) % mod;
}
void eadd(i64 &a, i64 b) {
    a = add(a, b);
}
void esub(i64 &a, i64 b) {
    a = sub(a, b);
}
void emul(i64 &a, i64 b) {
    a = mul(a, b);
}

i64 calcPaint(i64 x, i64 y) {
    return mul((1 + x) * x / 2 % mod, (1 + y) * y / 2 % mod);
}

int main() {
    int N;
    std::cin >> N;
    std::vector<std::pair<i64, i64>> P(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> P[i].first;
    }
    for (int i = 0; i < N; ++i) {
        std::cin >> P[i].second;
    }
    std::vector<i64> rW(N + 1);
    for (int i = 0; i < N; ++i) {
        rW[i + 1] = rW[i] + P[i].second;
    }
    auto calcRangeWidth = [&](const int l, const int r) {
        return rW[r] - rW[l];
    };
    
    std::map<i64, std::vector<i64>> eV;
    for (int i = 0; i < N; ++i) {
        eV[P[i].first].push_back(i);
    }
    std::set<std::tuple<i64, i64, i64>> rangeS; // (first, length)
    rangeS.insert({0, calcRangeWidth(0, N), 0});
    i64 answer = 0;
    for (const auto &[h, vec] : eV) {
        for (const int i : vec) {
            const auto p = calcRangeWidth(0, i);
            auto itr = rangeS.lower_bound({p + 1, 0, 0});
            assert(itr != rangeS.begin());
            --itr;
            
            // eval
            const auto [l, width, mh] = *itr;
            i64 a = calcPaint(h % mod, width % mod), b = calcPaint(mh % mod, width % mod);
            esub(a, b);
            eadd(answer, a);

            rangeS.erase(itr);
            i64 lw = p - l, rw = (l + width) - (p + P[i].second);
            if (lw != 0) {
                rangeS.insert({l, lw, h});
            }
            if (rw != 0) {
                rangeS.insert({p + P[i].second, rw, h});
            }
        }
    }
    std::cout << answer << std::endl;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 34 ms 2872 KB Output is correct
4 Correct 71 ms 4592 KB Output is correct
5 Correct 67 ms 5160 KB Output is correct
6 Correct 57 ms 4148 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 952 KB Output is correct
3 Correct 39 ms 2432 KB Output is correct
4 Correct 83 ms 4024 KB Output is correct
5 Correct 77 ms 4016 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 11 ms 852 KB Output is correct
4 Correct 42 ms 2292 KB Output is correct
5 Correct 80 ms 4012 KB Output is correct
6 Correct 81 ms 4040 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 11 ms 1816 KB Output is correct
9 Correct 48 ms 4284 KB Output is correct
10 Correct 106 ms 13844 KB Output is correct
11 Correct 101 ms 13764 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #6
18.0 / 18.0

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

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 33 ms 2872 KB Output is correct
12 Correct 70 ms 4660 KB Output is correct
13 Correct 69 ms 5180 KB Output is correct
14 Correct 58 ms 4196 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 11 ms 952 KB Output is correct
17 Correct 45 ms 2320 KB Output is correct
18 Correct 83 ms 4032 KB Output is correct
19 Correct 79 ms 4052 KB Output is correct
20 Correct 1 ms 352 KB Output is correct
21 Correct 10 ms 1760 KB Output is correct
22 Correct 46 ms 4264 KB Output is correct
23 Correct 97 ms 13764 KB Output is correct
24 Correct 110 ms 13752 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 16 ms 1812 KB Output is correct
31 Correct 13 ms 1876 KB Output is correct
32 Correct 48 ms 3056 KB Output is correct
33 Correct 81 ms 7988 KB Output is correct
34 Correct 183 ms 14788 KB Output is correct
35 Correct 96 ms 5312 KB Output is correct
36 Correct 180 ms 15360 KB Output is correct
37 Correct 189 ms 11224 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 131 ms 8524 KB Output is correct
40 Correct 130 ms 13632 KB Output is correct
41 Correct 118 ms 14108 KB Output is correct
42 Correct 105 ms 14148 KB Output is correct