oj.uz

Submission #716767

# Submission time Handle Problem Language Result Execution time Memory
716767 2023-03-31T04:29:36 Z Abrar_Al_Samit Meetings (IOI18_meetings) C++17
17 / 100
 87 ms 20288 KB 
#include <iostream>
#include <vector>
#include "meetings.h"
using namespace std;

const int nax = 1e5 + 3;
const int lg = 18;
const long long INF = 1e18;

int n;
int q;
int sp[nax][lg], an[nax][lg], aux[nax];
vector<int>h;

int get(int l, int r) {
	int msb = 31 - __builtin_clz(r-l+1);
	if(h[sp[l][msb]]>=h[sp[r-(1<<msb)+1][msb]])
		return sp[l][msb];
	return sp[r-(1<<msb)+1][msb];
}
int get2(int l, int r) {
	int msb = 31 - __builtin_clz(r-l+1);
	if(aux[an[l][msb]]>=aux[an[r-(1<<msb)+1][msb]])
		return an[l][msb];
	return an[r-(1<<msb)+1][msb];
}
vector<long long>minimum_costs(vector<int>H, vector<int>L, vector<int>R) {
	n = H.size();
	q = L.size();
	h = H;

	for(int i=0; i<n; ++i) {
		sp[i][0] = i;
	}
	for(int j=1; j<lg; ++j) {
		for(int i=0; i+(1<<j)-1<n; ++i) {
			if(H[sp[i][j-1]]>=H[sp[i+(1<<(j-1))][j-1]]) 
				sp[i][j] = sp[i][j-1];
			else 
				sp[i][j] = sp[i+(1<<(j-1))][j-1];
		}
	}
	for(int i=n-1; i>=0; --i) {
		if(H[i]==1) aux[i] = 1 + aux[i+1];
		an[i][0] = i;
	}
	for(int j=1; j<lg; ++j) {
		for(int i=0; i+(1<<j)-1<n; ++i) {
			if(aux[an[i][j-1]]>=aux[an[i+(1<<(j-1))][j-1]])
				an[i][j] = an[i][j-1];
			else 
				an[i][j] = an[i+(1<<(j-1))][j-1];
		}
	}

	vector<long long>ret(q);
	for(int i=0; i<q; ++i) {
		int mxID = get2(L[i], R[i]);
		int mxX = H[get(L[i], R[i])];
		if(mxX==1) {
			ret[i] = R[i] - L[i] + 1;
			continue;
		}
		int cnt;
		if(mxID+aux[mxID]-1>R[i]) {
			cnt = R[i] - mxID + 1;
			if(mxID!=L[i]) {
				mxID = get2(L[i], mxID-1);
				cnt = max(cnt, aux[mxID]);
			}
		} else {
			cnt = aux[mxID];
		}
		ret[i] = (R[i] - L[i] + 1 - cnt) * 1LL * mxX + cnt;
	}
	return ret;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 15.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 17 ms 3524 KB Output is correct
3 Correct 70 ms 20284 KB Output is correct
4 Correct 87 ms 20280 KB Output is correct
5 Correct 67 ms 20264 KB Output is correct
6 Correct 70 ms 20152 KB Output is correct
7 Correct 70 ms 20044 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 17 ms 3524 KB Output is correct
3 Correct 70 ms 20284 KB Output is correct
4 Correct 87 ms 20280 KB Output is correct
5 Correct 67 ms 20264 KB Output is correct
6 Correct 70 ms 20152 KB Output is correct
7 Correct 70 ms 20044 KB Output is correct
8 Incorrect 71 ms 20288 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

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