Submission #1233062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233062		LaMatematica14	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	67 ms	10568 KiB

fancyfence

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

const long long mod = 1000000007;

struct classcomp {
  bool operator() (const array<long long, 3> & lhs, const array<long long, 3>& rhs) const
  {if (lhs[0] != rhs[0]) return lhs[0]>rhs[0];
  else return lhs[1]<=rhs[1];}
};


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>, classcomp> seg;
    seg.insert({0, w[N], 0});
    long long tot = 0;
    for (int i = 0; i < N;) {
        array<long long, 3> tofind = {sec[i][1], sec[i][2], mod};
        array<long long, 3> x = *seg.upper_bound(tofind);
        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)%mod)*((x[1]-x[0])%mod)/2;
        r %= mod;
        r *= (((att)*(att+1) - x[2]*(x[2]+1))/2)%mod;
        tot += r%mod;
        tot %= mod;
        if (aus[1]-aus[0] > 0) seg.insert(aus);
    }
    cout << tot << "\n";
}

• 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