Submission #787175

#	Time	Username	Problem	Language	Result	Execution time	Memory
787175		APROHACK	Meetings (IOI18_meetings)	C++17	60 / 100	668 ms	60704 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define ss second
#define ff first
#define izquierda 0
#define derecha 1

using namespace std;
ll n, q;
ll nxtGrande[100002];	
ll anteriorGrande[100001];
ll dp[100001][2];
vector<int>height;



struct segTree{
	int dd, ht;
	ll maximo;
	ll donde;
	int mid;
	segTree *L, *R;
	segTree(int l, int r){
		dd = l;
		ht = r;
		mid = (dd + ht)/2;
		maximo = -1;
		donde = 0;
		if(l!=r){
			L = new segTree(l, mid);
			R = new segTree(mid+1, r);
			if(L->maximo > R->maximo){
				maximo = L->maximo;
				donde = L->donde;
			}else{
				maximo = R->maximo;
				donde = R->donde;
			}
		}else{
			maximo = height[l];
			donde = l;
		}
	}
	ll getMax(int l , int r){
		if( dd == l and r == ht){
			return maximo;
		}
		if( r <= mid ) return L->getMax(l, r);
		if( mid < l) return R->getMax(l, r);
		return max(L->getMax(l, mid), R->getMax(mid+1, r));
	}
	pair<ll, ll> query(int l, int r){
		if( dd == l and r == ht){
			return {donde, maximo};
		}
		if( r <= mid ) return L->query(l, r);
		if( mid < l) return R->query(l, r);
		pair<ll, ll> a = L->query(l, mid);
		pair<ll, ll> b = R->query(mid+1, r);
		if(a.ss > b.ss){
			return a;
		}else{
			return b;
		}
	}
};


struct seg1{
	int dd, ht;
	ll maximo;
	int mid;
	seg1 *L, *R;
	seg1(int l, int r){
		dd = l;
		ht = r;
		mid = (dd + ht)/2;
		maximo = -1;
		if(l!=r){
			L = new seg1(l, mid);
			R = new seg1(mid+1, r);
			
			if(L->maximo > R->maximo){
				maximo = L->maximo;
			}else{
				maximo = R->maximo;
			}
		}else{
			maximo = -1;
		}
	}
	
	void update(int pos, ll cuanto){
		if(dd == ht)maximo = max(maximo, cuanto);
		else if(pos <= mid)L->update(pos, cuanto);
		else R->update(pos, cuanto);
		if(dd != ht)maximo = max(L->maximo, R->maximo);
	}
	
	ll query(int l, int r){
		if( dd == l and r == ht){
			return maximo;
		}
		if( r <= mid ) return L->query(l, r);
		if( mid < l) return R->query(l, r);
		return max(L->query(l, mid), R->query(mid+1, r));
	}
};

struct segDp{
	int dd, ht;
	ll minimo;
	int mid;
	segDp *L, *R;
	segDp(int l, int r){
		dd = l;
		ht = r;
		mid = (dd + ht)/2;
		minimo = -1;
		if(l!=r){
			L = new segDp(l, mid);
			R = new segDp(mid+1, r);
			
			if(L->minimo < R->minimo){
				minimo = L->minimo;
			}else{
				minimo = R->minimo;
			}
		}else{
			minimo = dp[l][0] + dp[l][1] - height[l];
		}
	}
	
	void update(int pos, ll cuanto){
		if(dd == ht)minimo = min(minimo, cuanto);
		else if(pos <= mid)L->update(pos, cuanto);
		else R->update(pos, cuanto);
		if(dd != ht)minimo = max(L->minimo, R->minimo);
	}
	
	ll query(int l, int r){
		if( dd == l and r == ht){
			return minimo;
		}
		if( r <= mid ) return L->query(l, r);
		if( mid < l) return R->query(l, r);
		return min(L->query(l, mid), R->query(mid+1, r));
	}
};


std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	q = L.size();
	n = H.size();
	height = H;
	set<pair<ll, int> >alturas; // alturas  y indices.
	 bool all2 = true;
	 vector<ll>C;
	 for(int i = 0 ; i < n ; i ++)if(H[i] != 1 and H[i] != 2)all2 = false;
	 if(!all2){
		
		for(int i = n-1 ; i >= 0 ; i --){
			auto sig = alturas.upper_bound({H[i], n});
			if(sig == alturas.end())nxtGrande[i] = -1;
			else{
				nxtGrande[i] = (*sig).ss;

			}
			vector<pair<ll, int>>toE;
			for(auto j : alturas){
				if(j.ff > H[i])break;
				toE.pb(j);
			}
			for(auto j : toE)alturas.erase(j);
			alturas.insert({H[i], i});
		}
		alturas.clear();
		for(int i = 0 ; i < n ; i ++){
			auto sig = alturas.upper_bound({H[i], n});
			if(sig == alturas.end())anteriorGrande[i] = -1;
			else anteriorGrande[i] = (*sig).ss;
			vector<pair<ll, int>>toE;
			for(auto j : alturas){
				if(j.ff > H[i])break;
				toE.pb(j);
			}
			for(auto j : toE)alturas.erase(j);
			alturas.insert({H[i], i});
		}
		//for(int i = 0 ; i < n ; i++)cout << anteriorGrande[i] << " " ;
		//for(int i = 0 ; i < n ; i ++)cout << nxtGrande[i] << " ";
		
		for(ll i = n-1 ; i >= 0 ; i --){
			int sig = nxtGrande[i];
			if(sig == -1)dp[i][derecha] = (n-i)*H[i];
			else{
				dp[i][derecha] = (sig-i)*H[i] + dp[sig][derecha];
			}
		}
		
		
		for(ll i = 0 ; i < n ; i ++){
			int sig = anteriorGrande[i];
			if(sig == -1)dp[i][izquierda] = (i+1)*H[i];
			else{
				dp[i][izquierda] = (i-sig)*H[i] + dp[sig][izquierda];
			}
		}
		
		
		
		
		//for(int i = 0 ; i < n ; i ++)cout << dp[i][derecha] << " " ;
		//for(int i = 0 ; i < n ; i ++)cout << dp[i][izquierda] << " " ;
		segTree *st = new segTree(0, n-1);
		segDp *Sdp = new segDp(0, n-1);
		/*
		for(int query = 0 ; query < q; query ++){
			ll minimum = LLONG_MAX;
			//cout << "q = " << query << endl;
			for(int i = L[query] ; i <= R[query] ; i ++){
				ll k = st->query(i, R[query]).ff;
				ll der = dp[i][derecha] - dp[k][derecha] + (R[query]-k+1)*H[k];
				k = st->query(L[query], i).ff;
				ll izq = dp[i][izquierda] - dp[k][izquierda] + (k-L[query]+1)*H[k];
				minimum = min(minimum, der + izq - H[i]);
				//cout << i << " " << izq << " + " << der << endl;
			}
			C.pb(minimum);
		}
		* */
		for(int i = 0 ; i <= n ; i ++){
			if(nxtGrande[i] == -1)nxtGrande[i] = INT_MAX;
		}
		//for(int i = 0 ; i < n ; i ++)cout << dp[i][0] + dp[i][1] - height[i] << " " ;
		for(int query = 0 ; query < q; query ++){
			ll minimum = LLONG_MAX;
			ll maxIzq = H[L[query]];
			ll posMaxIzq = L[query];
			//cout << "q = " << query << endl;
			ll k, s;
			k = st->query(L[query], R[query]).ff;
			for(ll i = L[query] ; i <= R[query] ;){
				bool finish = false;
				//cout << "i = " << i << endl;
				
				s = posMaxIzq;
				//cout << s << " " << k << endl;
				//cout << nxtGrande[i] << " o " << k+1 << endl;
				ll siguientePos = min(nxtGrande[s], k + 1);
				if(siguientePos >= n)finish = true;
				siguientePos = min(siguientePos, n);
				
				ll suma = Sdp->query(i, siguientePos-1);
				//cout << "seg = " << suma << endl;
				suma += -dp[k][derecha] + (R[query]-k+1)*H[k];
				suma += -dp[s][izquierda] + (s-L[query]+1)*H[s];
				minimum = min(minimum, suma);
				/*
				ll der = dp[i][derecha] - dp[k][derecha] + (R[query]-k+1)*H[k];
				k = st->query(L[query], i).ff;
				ll izq = dp[i][izquierda] - dp[k][izquierda] + (k-L[query]+1)*H[k];
				minimum = min(minimum, der + izq - H[i]);
				//cout << i << " " << izq << " + " << der << endl;
				*/
				if(finish)break;
				if(siguientePos == nxtGrande[i]){
					maxIzq = H[nxtGrande[i]];
					posMaxIzq = nxtGrande[i];
				}
				if(siguientePos == k + 1){
					if(siguientePos <= R[query]){
						k = st->query(siguientePos, R[query]).ff;
					}
				}
				i = siguientePos;
			}
			C.pb(minimum);
		}
	}else{
		seg1 *st = new seg1(0, n-1);
		int lleva = 0, desde = -1;
		vector<pair<int, int>>conjuntitos;
		int pertenece[n+1];
		memset(pertenece, -1, sizeof pertenece);
		for(int i = 0 ; i < n ; i ++){
			if(H[i] == 2 and desde == -1)continue;
			if(H[i] == 2){
				conjuntitos.pb({desde, i-1});
				for(int j = desde ; j <= i-1 ; j ++)pertenece[j] = conjuntitos.size()-1;
				desde = -1;
				st->update(i-1, lleva);
				lleva = 0;
				
			}else{
				if(desde == -1){
					lleva = 1;
					desde = i;
				}else lleva ++ ;
			}
		}
		if(desde != -1){
			conjuntitos.pb({desde, n-1});
			for(int j = desde ; j <= n-1 ; j ++)pertenece[j] = conjuntitos.size()-1;
			desde = -1;
			st->update(n-1, lleva);
			lleva = 0;
			
		}		
		for(int query = 0 ; query < q ; query ++){
			//cout << "q " << query << endl;
			ll li = L[query], ls = R[query];
			ll total = R[query] - L[query] + 1;
			ll a = 0, b = 0;
			ll ans = LLONG_MAX;
			if(pertenece[li] == pertenece[ls] and pertenece[li] != -1){
				ans = min( ans, total);
				//cout << "mismo sitio" << endl;
			}else {
				if(H[li] == 1){
					a = conjuntitos[pertenece[li]].ss - L[query] + 1;
					li = conjuntitos[pertenece[li]].ss + 1;
				}
				if(H[ls] == 1){
					b = R[query]-conjuntitos[pertenece[ls]].ff + 1;
					ls = conjuntitos[pertenece[ls]].ff -1;
				}
				//cout << "cur " << ans  << " a " << a << " b " << b << endl;
				ans = min ( ans, (total-a)*2 + a);
				ans = min(ans, (total - b)*2 + b);
				//cout << "cur " << ans << endl;
				if(li <= ls){
					ll cu = st->query(li, ls);
					//cout << cu << endl;
					if(cu != -1) ans = min (ans, (total - cu)*2 + cu);
					else{
						ans = min(ans, total*2);
					}
				}
			}
			
			
			
			
			C.pb(ans);
		}
	}
	
	

	return C;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:241:7: warning: variable 'maxIzq' set but not used [-Wunused-but-set-variable]
  241 |    ll maxIzq = H[L[query]];
      |       ^~~~~~

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