Submission #768940

#	Time	Username	Problem	Language	Result	Execution time	Memory
768940		APROHACK	Wiring (IOI17_wiring)	C++14	100 / 100	91 ms	36892 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define pb push_back
#define pos first
#define color second
#define ll long long
using namespace std;
vector<pair<ll, bool> >nodes;
ll distNext[200001]; // Distancia de este nodo con el siguiente de otro color
ll distanciaAcum[200005]; // distancia acumulada si tomo desde i y lo uno con el siguiente del otro color
int siguiente[200005]; // siguiente del otro color

int nm;
ll mem[200005];
ll toPut[200005];


struct segTree{
	
	ll minimo, lazy;
	int dd, ht, mid;
	segTree *L, *R;
	segTree(int l, int r){
		dd = l, ht = r;
		mid = (dd + ht)/2;
		lazy = 0;
		minimo = 0;
		if(l == r){
			minimo = toPut[dd];
		}else{
			L = new segTree(l, mid);
			R = new segTree(mid+1, r);
			minimo = min(L->minimo, R->minimo);
		}
	}
	void propagate(){
		L->lazy += lazy;
		R->lazy += lazy;
		if(L->minimo != LLONG_MAX)L->minimo += lazy;
		if(R->minimo != LLONG_MAX)R->minimo += lazy;
		//L->minimo += lazy;
		//R->minimo += lazy;
		lazy = 0;
	}
	void update(int l, int r, ll value){
		if(l == dd and r == ht){
			lazy += value;
			if(minimo != LLONG_MAX)minimo += value;
			return ;
		}
		propagate();
		if(r <= mid){
			L->update(l, r, value);
		}else if(l > mid){
			R->update(l, r, value);
		}else{
			L->update(l, mid, value);
			R->update(mid+1, r, value);
		}
		minimo = min(L->minimo, R->minimo);
	}
	ll query(int l, int r){
		//cout << dd << " " << ht << " " << "query :" << l << " " << r << " " << minimo <<  endl;
		if(dd == l and r == ht)return minimo;
		propagate();
		if( r <= mid)return L->query(l, r);
		else if( mid < l)return R->query(l, r);
		else return min(L->query(l, mid), R->query(mid+1, r));
	}
};

ll dp(int node){
	
}

long long min_total_length(std::vector<int> r, std::vector<int> b) {
	memset(mem, -1, sizeof mem);
	int ir = r.size() -1, ib = 0;
	ll ans = 0;
	nm = r.size() + b.size();
	for(auto i : r)nodes.pb({i, 0});
	for(auto i : b)nodes.pb({i, 1});
	sort(nodes.begin(), nodes.end());
	ll last0 = -1, last1 = -1;
	int ultimo0 = -1, ultimo1 = -1;
	for(int i = nm-1 ; i >= 0 ; i --){
		if(nodes[i].color == 0){
			//cout << 0 << " ";
			if(last1-nodes[i].pos < 0){
				distNext[i] = -1;
			}else{
				distNext[i] = last1-nodes[i].pos;
			}
			last0 = nodes[i].pos;
			ultimo0 = i;
			siguiente[i] = ultimo1;
		}else{
			//cout << 1 << " ";
			if(last0-nodes[i].pos < 0){
				distNext[i] = -1;
			}else{
				distNext[i] = last0-nodes[i].pos;
			}
			last1 = nodes[i].pos;
			ultimo1 = i;
			siguiente[i] = ultimo0;
		}
		
	}
	ll distCum[2];
	distCum[0] = 0;
	distCum[1] = 0;
	for(int i = nm-1 ; i >= 0 ; i --){
		if(distNext[i] != -1){
			distCum[nodes[i].color] += distNext[i];
			distanciaAcum[i] = distCum[nodes[i].color];
		}else distanciaAcum[i] = -1;
		if(nodes[i].color == 0)distCum[1] = 0;
		else distCum[0] = 0;
	}
	
	bool currentColor = nodes[nm-1].color;
	int cuenta = 0, otraCuenta = 0;
	int idx = nm-1;
	mem[nm] = 0;
	for(; idx>= 0 ; idx --){
		if(nodes[idx].color != currentColor)break;
		cuenta ++;
		mem[idx] = LLONG_MAX;
	}
	
	
	for(; idx >= 0 ;){
		currentColor = nodes[idx].color;
		otraCuenta = 1;
		toPut[0] = 0;
		ll acum = 0;
		for(int i = 1 ; i <= cuenta ; i ++){ // agarrando i
			toPut[i] = acum;
			//if(mem[idx+i+1] == LLONG_MAX)toPut[i] = ((ll)INT_MAX) * 10000; /// caution
			if(min(mem[idx+i+1], mem[idx+i]) == LLONG_MAX)toPut[i] = LLONG_MAX;
			else toPut[i] += nodes[idx+i].pos-nodes[idx].pos + min(mem[idx+i+1], mem[idx+i]);
			acum += nodes[idx+i].pos-nodes[idx].pos;
			//cout << "tt " << i <<  " "  << toPut[i] << endl;
		}
		segTree *currentState = new segTree(1, cuenta);
		//cout << "FROM " << idx << endl;
		//for(int i = 1 ; i <= cuenta ; i ++)cout << " taking " << i << ": " << currentState->query(i, i) <<endl;
		mem[idx] = currentState->query(1, cuenta);
		//cout << "ans for " << idx << " = " << mem[idx] << endl;
		idx--;
		while(nodes[idx].color == currentColor){
			otraCuenta ++ ;
			currentState->update(1, min(otraCuenta-1, cuenta), nodes[siguiente[idx]].pos - nodes[idx].pos);
			if(min(otraCuenta-1, cuenta) + 1 <= cuenta){
				currentState->update(min(otraCuenta-1, cuenta) + 1, cuenta, nodes[siguiente[idx]-1].pos - nodes[idx].pos);
			}
			//cout << "FROM " << idx << endl;
			//for(int i = 1 ; i <= cuenta ; i ++)cout << " taking " << i << ": " << currentState->query(i, i) <<endl;
			mem[idx] = currentState->query(1, cuenta);
			//cout << "ans for " << idx << " = " << mem[idx] << endl;
			idx--;
		}
		cuenta = otraCuenta;
		
	}
	
	
	return mem[0];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int dp(int)':
wiring.cpp:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
   74 | }
      | ^
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:78:6: warning: unused variable 'ir' [-Wunused-variable]
   78 |  int ir = r.size() -1, ib = 0;
      |      ^~
wiring.cpp:78:24: warning: unused variable 'ib' [-Wunused-variable]
   78 |  int ir = r.size() -1, ib = 0;
      |                        ^~
wiring.cpp:79:5: warning: unused variable 'ans' [-Wunused-variable]
   79 |  ll ans = 0;
      |     ^~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45