제출 #1073743

#제출 시각아이디문제언어결과실행 시간메모리
1073743shezitt모임들 (IOI18_meetings)C++14
0 / 100
5553 ms2904 KiB
#include <bits/stdc++.h> #include "meetings.h" using ll = long long; #define fore(a, b, c) for(int a=b; a<c; ++a) #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() using namespace std; struct segtree { int n; vector<ll> T; segtree(int n) : n(n) { T.assign(4*n+2, 0); } void update(int i, int tl, int tr, int idx, int val){ if(tl == tr){ T[i] = val; return; } int tm = (tl + tr) / 2; if(idx <= tm){ update(2*i+1, tl, tm, idx, val); } else { update(2*i+2, tm+1, tr, idx, val); } T[i] = max(T[2*i+1], T[2*i+2]); } void update(int idx, int val){ update(0, 0, n-1, idx, val); } ll query(int i, int tl, int tr, int l, int r){ if(l <= tl && tr <= r){ return T[i]; } if(r < tl or tr < l){ return 0; } int tm = (tl + tr) / 2; ll p1 = query(2*i+1, tl, tm, l, r); ll p2 = query(2*i+2, tm+1, tr, l, r); return max(p1, p2); } ll query(int l, int r){ return query(0, 0, n-1, min(l,r), max(l,r)); } }; std::vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) { int Q = L.size(); vector<ll> C(Q); int N = 0; for (int j = 0; j < Q; ++j) { N = max(N, R[j]); } N++; assert(N<=3000); segtree T(N); for(int i=0; i<N; ++i){ T.update(i, H[i]); } for(int j=0; j<Q; ++j){ int l = L[j], r = R[j]; ll ans = 4e18; for(int x=l; x<=r; ++x){ ll cur = 0; for(int i=l; i<=r; ++i){ cur += T.query(i, x); } ans = min(ans, cur); } C[j] = ans; } return C; }
#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...