oj.uz

답안 #787175

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
787175 2023-07-18T22:32:35 Z APROHACK 모임들 (IOI18_meetings) C++17
60 / 100
 668 ms 60704 KB 
#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

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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 2 ms 1080 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 2 ms 1092 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 2 ms 1080 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 2 ms 1092 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 15 ms 1876 KB Output is correct
11 Correct 12 ms 1876 KB Output is correct
12 Correct 14 ms 1876 KB Output is correct
13 Correct 8 ms 1876 KB Output is correct
14 Correct 6 ms 1968 KB Output is correct
15 Correct 18 ms 1960 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 28 ms 2544 KB Output is correct
3 Correct 89 ms 14196 KB Output is correct
4 Correct 60 ms 14072 KB Output is correct
5 Correct 51 ms 14284 KB Output is correct
6 Correct 56 ms 14064 KB Output is correct
7 Correct 57 ms 14060 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 28 ms 2544 KB Output is correct
3 Correct 89 ms 14196 KB Output is correct
4 Correct 60 ms 14072 KB Output is correct
5 Correct 51 ms 14284 KB Output is correct
6 Correct 56 ms 14064 KB Output is correct
7 Correct 57 ms 14060 KB Output is correct
8 Correct 366 ms 29392 KB Output is correct
9 Correct 149 ms 31172 KB Output is correct
10 Correct 292 ms 31180 KB Output is correct
11 Correct 383 ms 31184 KB Output is correct
12 Correct 177 ms 31144 KB Output is correct
13 Correct 342 ms 31224 KB Output is correct
14 Correct 241 ms 31156 KB Output is correct
15 Correct 668 ms 31120 KB Output is correct
16 Correct 323 ms 31224 KB Output is correct

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 2 ms 1080 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 2 ms 1092 KB Output is correct
8 Correct 2 ms 1108 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 15 ms 1876 KB Output is correct
11 Correct 12 ms 1876 KB Output is correct
12 Correct 14 ms 1876 KB Output is correct
13 Correct 8 ms 1876 KB Output is correct
14 Correct 6 ms 1968 KB Output is correct
15 Correct 18 ms 1960 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 28 ms 2544 KB Output is correct
18 Correct 89 ms 14196 KB Output is correct
19 Correct 60 ms 14072 KB Output is correct
20 Correct 51 ms 14284 KB Output is correct
21 Correct 56 ms 14064 KB Output is correct
22 Correct 57 ms 14060 KB Output is correct
23 Correct 366 ms 29392 KB Output is correct
24 Correct 149 ms 31172 KB Output is correct
25 Correct 292 ms 31180 KB Output is correct
26 Correct 383 ms 31184 KB Output is correct
27 Correct 177 ms 31144 KB Output is correct
28 Correct 342 ms 31224 KB Output is correct
29 Correct 241 ms 31156 KB Output is correct
30 Correct 668 ms 31120 KB Output is correct
31 Correct 323 ms 31224 KB Output is correct
32 Runtime error 216 ms 60704 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -