Submission #97350

#	Time	Username	Problem	Language	Result	Execution time	Memory
97350		E869120	Meetings (IOI18_meetings)	C++14	60 / 100	5536 ms	117884 KiB

meetings

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

class RangeMinimumQuery {
	public:
	vector<long long> dat; int size_;
	
	void init(int sz) {
		size_ = 1;
		while (size_ < sz) size_ *= 2;
		dat.resize(size_ * 2, 0LL);
	}
	void update(int p, long long x) {
		p += size_; dat[p] = x;
		while (p >= 2) {
			p >>= 1;
			dat[p] = min(dat[p * 2], dat[p * 2 + 1]);
		}
	}
	long long query_(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) return dat[u];
		if (b <= l || r <= a) return 0LL;
		
		long long c1 = query_(l, r, a, (a + b) >> 1, u * 2);
		long long c2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return min(c1, c2);
	}
	long long query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

class RangeMaximumQuery {
	public:
	vector<long long> dat; int size_;
	
	void init(int sz) {
		size_ = 1;
		while (size_ < sz) size_ *= 2;
		dat.resize(size_ * 2, 0LL);
	}
	void update(int p, long long x) {
		p += size_; dat[p] = x;
		while (p >= 2) {
			p >>= 1;
			dat[p] = max(dat[p * 2], dat[p * 2 + 1]);
		}
	}
	long long query_(int l, int r, int a, int b, int u) {
		if (l <= a && b <= r) return dat[u];
		if (b <= l || r <= a) return 0LL;
		
		long long c1 = query_(l, r, a, (a + b) >> 1, u * 2);
		long long c2 = query_(l, r, (a + b) >> 1, b, u * 2 + 1);
		return max(c1, c2);
	}
	long long query(int l, int r) {
		return query_(l, r, 0, size_, 1);
	}
};

long long N, Q, H[750009], T[750009], sm[750009]; pair<int, int> dp[5009][5009];

void dfs(int cl, int cr) {
	if (cl > cr) return;
	int cm = dp[cl][cr].second; long long cost = dp[cl][cr].first;
	//cout << "cl = " << cl << ", cr = " << cr << ", cm = " << cm << ", cost = " << cost << endl;
	T[cl] += cost * (cr - cm + 1);
	T[cm] += cost * (cm - cl);
	T[cm + 1] -= cost * (cr - cm);
	T[cr + 1] -= cost * (cm - cl + 1);
	dfs(cl, cm - 1);
	dfs(cm + 1, cr);
}

long long ranged(long long cl, long long cr) {
	return sm[cr] - sm[cl];
}

vector<long long> minimum_costs(vector<int> HH, vector<int> L, vector<int> R) {
	int maxh = 0; for (int i = 0; i < HH.size(); i++) maxh = max(maxh, HH[i]);
	
	if(maxh <= 20) {
		// -------------------------------------- Initialize / Precalc Phase -------------------------
		N = HH.size(); Q = L.size();
		for (int i = 0; i < N; i++) H[i] = HH[i];
		for (int i = 0; i < N; i++) sm[i + 1] = sm[i] + H[i];
		
		vector<long long> DD[21];
		for (int i = 0; i < 21; i++) DD[i].clear();
		for (int i = 0; i < N; i++) {
			for (int j = 1; j <= H[i]; j++) DD[j].push_back(i);
		}
		
		RangeMaximumQuery Z[21], ZZ; ZZ.init(N + 2);
		for (int i = 0; i < N; i++) ZZ.update(i, H[i]);
		
		for (int i = 0; i < 21; i++) Z[i].init(N + 2);
		for (int i = 0; i < N; i++) {
			for (int j = 1; j <= H[i]; j++) Z[j].update(i, 0);
			
			long long sss = 0;
			for (int j = H[i] + 1; j <= 20; j++) {
				int pos1 = lower_bound(DD[j].begin(), DD[j].end(), i) - DD[j].begin();
				int pl = -1, pr = N;
				if (DD[j].size() >= 1){
					if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
				}
				sss += (pr - pl - 1); //cout << i << " : " << j << ", " << sss << endl;
				Z[j].update(i, sss);
			}
		}
		
		// ------------------------------ Final Query Calculation Part ----------------------------
		
		vector<long long> ans;
		for (int t = 0; t < Q; t++) {
			long long LL[22], RR[22], maxp = ZZ.query(L[t], R[t] + 1);
			
			for (int i = 1; i <= maxp; i++) {
				int pos1 = lower_bound(DD[i].begin(), DD[i].end(), L[t]) - DD[i].begin();
				LL[i] = DD[i][pos1];
			}
			for (int i = 1; i <= maxp; i++) {
				int pos1 = lower_bound(DD[i].begin(), DD[i].end(), R[t] + 1) - DD[i].begin(); pos1--;
				RR[i] = DD[i][pos1];
			}
			LL[maxp + 1] = R[t] + 1; RR[maxp + 1] = L[t] - 1;
			
			// Leftmost Part
			long long minx = (1LL << 60);
			for (int i = 1; i <= maxp - 1; i++) {
				long long Z1 = Z[i].query(LL[i], LL[i + 1]);
				long long Z2 = 0; for (int j = i + 1; j <= maxp; j++) Z2 += 1LL * j * (LL[j + 1] - LL[j]);
				long long Z3 = 1LL * i * (LL[i + 1] - L[t]) - Z1;
				minx = min(minx, Z2 + Z3); //cout << i << " " << LL[i] << " " << LL[i + 1] << " " << Z1 << " " << Z2 << " " << Z3 << endl;
			}
			for (int i = 1; i <= maxp - 1; i++) {
				long long Z1 = Z[i].query(RR[i + 1] + 1, RR[i] + 1);
				long long Z2 = 0; for (int j = i + 1; j <= maxp; j++) Z2 += 1LL * j * (RR[j] - RR[j + 1]);
				long long Z3 = 1LL * i * (R[t] - RR[i + 1]) - Z1;
				minx = min(minx, Z2 + Z3);
			}
			long long Z1 = Z[maxp].query(LL[maxp], RR[maxp] + 1);
			long long Z2 = 1LL * maxp * (R[t] - L[t] + 1) - Z1;
			minx = min(minx, Z2);
			ans.push_back(minx);
		}
		return ans;
	}
	else{
		N = HH.size(); Q = L.size();
		for (int i = 0; i < N; i++) H[i] = HH[i];
		
		for (int i = 0; i < N; i++) {
			pair<int, int> BASE = make_pair(-1, -1);
			for (int j = i; j < N; j++) {
				BASE = max(BASE, make_pair((int)H[j], j));
				dp[i][j] = BASE;
			}
		}
		
		vector<long long> ans;
		for (int i = 0; i < Q; i++) {
			for (int j = 0; j <= N; j++) T[j] = 0;
			dfs(L[i], R[i]);
			for (int j = 1; j <= N; j++) T[j] += T[j - 1];
			
			long long rem = (1LL << 60);
			for (int j = L[i]; j <= R[i]; j++) rem = min(rem, T[j]);
			ans.push_back(rem);
		}
		return ans;
	}
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:82:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  int maxh = 0; for (int i = 0; i < HH.size(); i++) maxh = max(maxh, HH[i]);
                                ~~^~~~~~~~~~~
meetings.cpp:108:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
      if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
      ^~
meetings.cpp:108:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
      if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
                                           ^~
meetings.cpp:108:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (pos1 >= 1) pl = DD[j][pos1 - 1]; if (pos1 < DD[j].size()) pr = DD[j][pos1];
                                               ~~~~~^~~~~~~~~~~~~~

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