Submission #1217501

#TimeUsernameProblemLanguageResultExecution timeMemory
1217501perekopskadMeetings (IOI18_meetings)C++20
4 / 100
5594 ms2020 KiB
#pragma GCC optimize ("Ofast") #include "meetings.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; #define el '\n' #define pb push_back #define pii pair <ll, ll> #define ff first #define ss second #define mkp make_pair #define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++) #define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--) template<class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template<class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } ll const N = 8e5 + 10; ll const LOG = 22; ll const inf = 1e9 + 10; ll const INF = 1e18 + 10; ll const mod = 1e9 + 7; ll const mod2 = 998244353; ll const K = 400; ll n, q; ll a[N], c[N], t[4 * N], w[4 * N]; void push(ll i, ll tl, ll tr) { if(w[i] == -1) return; ll mid = (tl + tr) / 2; w[i + i] = w[i]; w[i + i + 1] = w[i]; t[i + i] = (mid - tl + 1) * w[i]; t[i + i + 1] = (tr - mid) * w[i]; w[i] = -1; } void update(ll i, ll tl, ll tr, ll l, ll r, ll val) { if(tr < l || r < tl) return; if(l <= tl && tr <= r) { t[i] = (tr - tl + 1) * val; w[i] = val; return; } push(i, tl, tr); ll mid = (tl + tr) / 2; update(i + i, tl, mid, l, r, val); update(i + i + 1, mid + 1, tr, l, r, val); t[i] = t[i + i] + t[i + i + 1]; } ll get(ll i, ll tl, ll tr, ll l, ll r) { if(tr < l || r < tl) return 0; if(l <= tl && tr <= r) return t[i]; push(i, tl, tr); ll mid = (tl + tr) / 2; return get(i + i, tl, mid, l, r) + get(i + i + 1, mid + 1, tr, l, r); } ll calc(ll l, ll r) { stack <ll> st; a[0] = INF; st.push(0); fill(w, w + 4 * n, -1); fill(t, t + 4 * n, 0); fr(i, l, r) { while(a[st.top()] < a[i]) st.pop(); ll x = max(st.top() + 1, l); update(1, 1, n, x, i, a[i]); c[i] += get(1, 1, n, l, i); st.push(i); } fill(w, w + 4 * n, -1); fill(t, t + 4 * n, 0); while(!st.empty()) st.pop(); a[n + 1] = INF; st.push(n + 1); frb(i, r, l) { while(a[st.top()] < a[i]) st.pop(); ll x = min(st.top() - 1, r); update(1, 1, n, i, x, a[i]); c[i] += get(1, 1, n, i, r); st.push(i); c[i] -= a[i]; } ll ans = INF; fr(i, l, r) { chmin(ans, c[i]); c[i] = 0; } return ans; } std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) { n = H.size(), q = L.size(); fr(i, 1, n) a[i] = H[i - 1]; fill(w, w + 4 * n, -1); fill(t, t + 4 * n, 0); vector <ll> ans; fr(i, 0, q - 1) { ans.pb(calc(L[i] + 1, R[i] + 1)); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...