Submission #1233033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233033		LaMatematica14	Fancy Fence (CEOI20_fancyfence)	C++20	0 / 100	1096 ms	328 KiB

fancyfence

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

const long long mod = 1000000007;


int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int N; cin >> N;
    vector<long long> h(N), w(N+1);
    for (int i = 0; i < N; i++) cin >> h[i];
    for (int i = 0; i < N; i++) cin >> w[i+1];
    for (int i = 1; i <= N; i++) {
        w[i] += w[i-1];
    }
    vector<array<long long, 3>> sec(N);
    for (int i = 0; i < N; i++) {
        sec[i] = {h[i], w[i], w[i+1]};
    }
    sort(sec.begin(), sec.end());

    set<array<long long, 3>, less<array<long long,3>>> seg;
    seg.insert({0, w[N], 0});
    long long tot = 0;
    for (int i = 0; i < N;) {
        array<long long, 3> x = *seg.upper_bound({sec[i][1], sec[i][2], 0});
        seg.erase(x);
        long long beg = x[0];
        long long att = sec[i][0];
        array<long long, 3> aus;
        while (sec[i][0] == att && sec[i][1] <= x[1]) {
            if (sec[i][1]-beg > 0) seg.insert({beg, sec[i][1], att});
            beg = sec[i][2];
            aus = {beg, x[1], att};
            i++;
        }
        long long r = (x[1]-x[0]+1)*(x[1]-x[0])/2;
        r %= mod;
        r *= (att-x[2]+1)*(att)/2;
        r %= mod;
        tot += r;
        tot %= mod;
        if (aus[1]-aus[0] > 0) seg.insert(aus);
    }
    cout << tot << "\n";
}

• 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