Submission #167096

#	Time	Username	Problem	Language	Result	Execution time	Memory
167096		Mounir	Meetings (IOI18_meetings)	C++14	0 / 100	3 ms	376 KiB

meetings

#include <bits/stdc++.h>
using namespace std;

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	vector<long long> coutsMin;
	int nMonts =  H.size(), nReqs = R.size();
	vector<int> hauteurs = H;
	vector<int> droite(nMonts), gauche(nMonts), taille(nMonts);
	
	int pt = -1;
	for (int iMont = 0; iMont < nMonts; ++iMont){
		if (hauteurs[iMont] != 0)
			pt = iMont;
		gauche[iMont] = pt;
	}
	pt = nMonts;
	for (int iMont = nMonts - 1; iMont >= 0; --iMont){
		if (hauteurs[iMont] != 0)
			pt = iMont;
		droite[iMont] = pt;
	}
	
	for (int iMont = 0; iMont < nMonts; ++iMont)
		taille[iMont] = droite[iMont] - gauche[iMont] - 1;
	int tTree = (1 << ((int)ceil(log2(nMonts))));
	vector<int> tree(tTree * 2);
	for (int &noeud : tree)
		noeud = 0;
	for (int i = 0; i < nMonts; ++i)
		tree[i + tTree] = taille[i];
	for (int i = tTree - 1; i > 0; --i)
		tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
	
	for (int iReq = 0; iReq < nReqs; ++iReq){
		int gaucheReq = L[iReq], droiteReq = R[iReq], tailleInter = droiteReq - gaucheReq - 1;
		int minimum = 750000;
		minimum = min(minimum, tailleInter - (droite[gaucheReq] - gaucheReq));
		gaucheReq = droite[gaucheReq ] + 1;
		minimum = min(minimum, tailleInter - (droiteReq - gauche[droiteReq]));
		droiteReq = gauche[droiteReq] - 1;
		
		int maxCouvert = 0;
		while (droite > gauche){
			if (gaucheReq%2 == 1){
				maxCouvert = max(maxCouvert, tree[gaucheReq]);
				gaucheReq++;
				continue;
			}
			if (droiteReq%2 == 0){
				maxCouvert = max(maxCouvert, tree[droiteReq]);
				droiteReq--;
				continue;
			}
			droiteReq /= 2;
			gaucheReq /= 2;
		}
		
		minimum = min(minimum, tailleInter - maxCouvert);
		coutsMin.push_back(minimum);
	}
	return coutsMin;
}

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