| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1009653 | aaaaaarroz | Meetings (IOI18_meetings) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct nodo{
ll suma;
ll respuesta;
ll prefijo;
ll sufijo;
};
template<class T>
struct SegmentTree{
T (*merge)(T, T);
ll n;
vector<T>ST;
void build(ll i, ll l, ll r, vector<T> &values){
if (l == r){
ST[i] = values[l];
return;
}
build(i * 2, l, (l + r) / 2, values);
build(i * 2 + 1, (l + r) / 2 + 1, r, values);
ST[i] = merge(ST[i * 2], ST[i * 2 + 1]);
}
SegmentTree(vector<T> &values, T (*merge)(T a, T b)) : merge(merge){
n = values.size();
ST.resize(n << 2 | 3);
build(1, 0, n - 1, values);
}
void update(ll i, ll l, ll r, ll pos, T val){
if (r < pos or l > pos) return;
if (l == r){
ST[i] = val;
return;
}
update(i << 1, l, (l + r) >> 1, pos, val);
update(i << 1 | 1, (l + r) / 2 + 1, r, pos, val);
ST[i] = merge(ST[i << 1], ST[i << 1 | 1]);
}
void update(ll pos, T val){
update(1, 0, n - 1, pos, val);
}
T query(ll i, ll l, ll r, ll a, ll b){
if (l >= a and r <= b) return ST[i];
ll mid = (l + r) >> 1;
if (mid < a)
return query(i << 1 | 1, mid + 1, r, a, b);
if (mid >= b)
return query(i << 1, l, mid, a, b);
return merge(query(i << 1, l, mid, a, b), query(i << 1 | 1, mid + 1, r, a, b));
}
T query(ll a, ll b){
if (a > b) return merge(query(1, 0, n - 1, 0, b), query(1, 0, n - 1, a, n - 1));
return query(1, 0, n - 1, a, b);
}
};
nodo merge(nodo a,nodo b){
nodo c;
c.suma=a.suma+b.suma;
c.prefijo=max(a.prefijo,a.suma+b.prefijo);
c.sufijo=max(b.sufijo,b.suma+a.sufijo);
c.respuesta=max({a.sufijo+b.prefijo,a.respuesta,b.respuesta});
return c;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
ll n=H.size();
ll Q = L.size();
vector<ll> C(Q);
vector<ll>nuevo=H;
for(ll i=0;i<n;i++){
if(nuevo[i]==2){
nuevo[i]=-INT_MAX;
}
}
SegmentTree<nodo>st(nuevo,merge);
for(ll q=0;q<Q;q++){
ll l=L[q];
ll r=R[q];
ll maxsequenceofones=st.query(l,r);
if(maxsequenceofones<=0){
C[q]=2*(r-l+1);
}
else{
ll falta=(r-l+1)-(maxsequenceofones);
C[q]=(maxsequenceofones+(2*falta));
}
}
return C;
}