Submission #97342

#	Time	Username	Problem	Language	Result	Execution time	Memory
97342		E869120	Meetings (IOI18_meetings)	C++14	36 / 100	2021 ms	426488 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 (1LL << 60);
		
		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 -(1LL << 60);
		
		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]; 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);
}

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 <= 2) {
		N = HH.size(); Q = L.size();
		for (int i = 0; i < N; i++) H[i] = HH[i];
		
		vector<long long> D2;
		for (int i = 0; i < N; i++) { if (H[i] == 2) D2.push_back(i); }
		
		RangeMaximumQuery Z; Z.init(N + 2);
		for (int i = 0; i < N; i++) {
			if (H[i] == 2) Z.update(i, 0);
			else {
				int pos1 = lower_bound(D2.begin(), D2.end(), i) - D2.begin();
				int pos0 = pos1 - 1;
				
				int cr = N - 1; if (pos1 < D2.size()) cr = D2[pos1] - 1;
				int cl = 0; if (pos0 >= 0) cl = D2[pos0] + 1;
				Z.update(i, cr - cl + 1);
			}
		}
		
		vector<long long> ans;
		for (int i = 0; i < Q; i++) {
			int pos1 = lower_bound(D2.begin(), D2.end(), L[i]) - D2.begin();
			int pos2 = lower_bound(D2.begin(), D2.end(), R[i] + 1) - D2.begin();
			if (pos1 == pos2) ans.push_back(R[i] - L[i] + 1);
			else {
				int pl = D2[pos1], pr = D2[pos2 - 1];
				long long R1 = Z.query(pl, pr + 1);
				long long R2 = (pl - L[i]);
				long long R3 = (R[i] - pr);
				ans.push_back((2LL * (R[i] - L[i] + 1LL)) - max({R1, R2, R3}));
			}
		}
		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:78: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:94:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     int cr = N - 1; if (pos1 < D2.size()) cr = D2[pos1] - 1;
                         ~~~~~^~~~~~~~~~~

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