제출 #1144050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144050		alexthefirelord	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	50 ms	6668 KiB

fancyfence

#pragma GCC optimize("Ofast,inline,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
// #define TXT
#define FILENAME ""

#ifdef TXT
struct FileOpener {
	FileOpener() {
		freopen(FILENAME".in", "r", stdin);
		freopen(FILENAME".out", "w", stdout);
	}
} fileopener;
#endif

using ll   = int64_t;
using ull  = uint64_t;
using vi   = vector<ll>;
using vvi  = vector<vector<ll>>;
using ii   = pair<ll,ll>;
using vii  = vector<ii>;
using vvii = vector<vector<ii>>;

#define fore(i,b,e)  for (int64_t i = (b); i < (e); ++i)
#define foree(i,b,e) for (int64_t i = (b); i <= (e); ++i)
#define ford(i,b,e)  for (int64_t i = (e)-1; i >= (b); --i)
#define fordd(i,b,e) for (int64_t i = (e); i >= (b); --i)
#define ff first
#define ss second
#define pb push_back
#define pob pop_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define fastIO ios::sync_with_stdio(false)
#define ceilll(n,d) (((n)+(d)-1)/(d))
#define print_arr(arr,b,e) {fore(i,(b),(e)) cout << arr[i] << ' '; cout << '\n';}
#define id(x) #x
 
const double PI = 3.1415926535897932;
const double EPS = 1e-9;
constexpr ll INF = 1e18;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// Memory measurement: command time -f '\nTime: %e s  Memory: %M KB' ./exe
 
inline ull gcd(ull a, ull b) {
    while (a&&b)
        a>b?a%=b:b%=a;
    return a?a:b;
}

inline ull lcm(ull a, ull b) {
    return a/gcd(a,b)*b;
}
 
inline ull power(ull a, ll b) {
    ull ans = 1;
    while (b) {
        if (b&1) ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}

inline ull powmod(ull a, ll b, ull _mod) {
    ull ans = 1;
    a %= _mod;
    while (b) {
        if (b&1) ans = (ans * a) % _mod;
        a = (a * a) % _mod;
        b >>= 1;
    }
    return ans;
}
 
ll phi(ll n) {
    ll m;

    m = n;
    for(ll i = 2; i*i <= m; ++i) {
        if (m % i == 0) {
            n = n/i*(i-1);
            while (m % i == 0)
                m /= i;
        }
    }
    if (m != 1)
        n = n/m*(m-1);
        
    return n;
}
 
ull phi(ull n) {
    ull m;

    m = n;
    for(ull i = 2; i*i <= m; ++i) {
        if (m % i == 0) {
            n = n/i*(i-1);
            while (m % i == 0)
                m /= i;
        }
    }
    if (m != 1)
        n = n/m*(m-1);
        
    return n;
}
 
inline ull num_of_digits(ull n) {
    ll ans = 0;
    while (n) {
        n /= 10;
        ++ans;
    }
    return ans;
}
 
inline ull num_of_digits_b(ull n) {
    ll ans = 0;
    while (n) {
        n >>= 1;
        ++ans;
    }
    return ans;
}

bool is_prime(ll n) {
    for (ll i = 2; i*i <= n; ++i)
        if (n % i == 0) return false;
    return true;
}

ull mr_mult_mod(ull a, ull b, ull mod) {
    ull ans = 0;
    while (b) {
        if (b&1) ans = (ans+a) % mod;
        a = (a << 1) % mod;
        b >>= 1;
    }
    return ans;
}

ull mr_pow_mod(ull a, ull p, ull mod) {
    ull ans = 1;
    while (p) {
        if (p&1) ans = mr_mult_mod(ans, a, mod);
        a = mr_mult_mod(a, a, mod);
        p >>= 1;
    }
    return ans;
}

bool miller_rabin(ull n) {
    if (n == 2)
        return true;
    if (n < 2 || n % 2 == 0)
        return false;

    ull nn = n-1;
    ull s = 0, d;
    while (nn % 2 == 0)
        ++s, nn /= 2;
    d = nn;
    const vector<ull> primes{2,3,5,7,11,13,17,19,23,29,31,37};

    for (ull a : primes) {
        if (a == n) return true;
        ull x = mr_pow_mod(a, d, n);
        ull y;
        fore(i, 0, s) {
            y = mr_mult_mod(x, x, n);
            if (y == 1 && x != 1 && x != n-1)
                return false;
            x = y;
        }
        if (y != 1)
            return false;
    }
    return true;
}

////////////////////////////////////////////
// SOLUTION //

// #define MULTITEST
// #define GENERATE_TEST
// #define CHECK_ANSWER

void precalc() {
}

struct seg {
    ll l,r,h;
    bool operator<(const seg &o) const {
        return h > o.h;
    }
};

const ll mod = 1000000007;

ll cn2(ll n) {
    n %= mod;
    return n*(n+1)/2%mod;
}

void solve() {
    ll n; cin >> n;
    vi h(n), w(n);
    vector<seg> s(n);
    ll x = 0;
    fore(i,0,n) cin >> h[i];
    fore(i,0,n) {
        cin >> w[i];
        s[i] = {x, x+w[i], h[i]};
        x += w[i];
    }
    s.pb({-1,-1,0});
    
    sort(all(s));
    ll ans = 0, last = -1;
    set<ii> segs;
    ll sum = 0;
    auto insert = [&](ll l, ll r) {
        auto nit = segs.lower_bound({l,r});
        auto pit = segs.end();
        if (nit != segs.begin()) pit = prev(nit);
        if (nit != segs.end() && nit->ff == r) {
            (sum += mod - cn2(nit->ss - nit->ff)) %= mod;
            r = nit->ss;
            segs.erase(nit);
        }
        if (pit != segs.end() && pit->ss == l) {
            (sum += mod - cn2(pit->ss - pit->ff)) %= mod;
            l = pit->ff;
            segs.erase(pit);
        }
        (sum += cn2(r - l)) %= mod;
        segs.insert({l,r});
    };
    for (const auto &[l,r,h] : s) {
        if (h != last) {
            (ans += sum * (cn2(last) - cn2(h) + mod) % mod) %= mod;
        }
        insert(l,r);
        last = h;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout.precision(12);
    
    precalc();

#ifdef MULTITEST
    ll t;
    cin >> t;
    while (t--)
    #endif
        solve();
    return 0;
}

• 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