제출 #1009655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009655		aaaaaarroz	모임들 (IOI18_meetings)	C++17	17 / 100	63 ms	21696 KiB

meetings

#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<nodo>nuevo;
  for(ll i=0;i<n;i++){
	  nodo anadir;
	  if(H[i]==2){
		  anadir.suma=-INT_MAX;
		  anadir.respuesta=-INT_MAX;
		  anadir.prefijo=-INT_MAX;
		  anadir.sufijo=-INT_MAX;
		  nuevo.push_back(anadir);
	  }
	  else{
		  anadir.suma=1;
		  anadir.respuesta=1;
		  anadir.prefijo=1;
		  anadir.sufijo=1;
		  nuevo.push_back(anadir);
	  }
  }
  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).respuesta;
	  if(maxsequenceofones<=0){
		  C[q]=2*(r-l+1);
	  }
	  else{
		  ll falta=(r-l+1)-(maxsequenceofones);
		  C[q]=(maxsequenceofones+(2*falta));
	  }
  }
  return C;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40