oj.uz

Submission #167096

# Submission time Handle Problem Language Result Execution time Memory
167096 2019-12-05T14:54:46 Z Mounir Meetings (IOI18_meetings) C++14
0 / 100
 3 ms 376 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -